How to Check if 1s are Equidistant in a Binary String in Python

Learn how to verify if all '1' characters in a binary string maintain equal spacing by calculating index gaps and comparing them in Python.

Given a binary string like "1001001", determine if the distance (gap) between every consecutive 1 is the same. This problem appears in pattern recognition, signal processing, and coding challenges.

Understanding the Problem

String: "1001001"
Positions:  0  3  6
Gaps:        3  3

All gaps equal → True (equidistant)

String: "101001"
Positions:  0  2  5
Gaps:        2  3

Gaps differ → False (not equidistant)

Using Index Collection

The standard approach:

Find the index of every 1
Calculate the differences between consecutive indices
Check if all differences are equal

def has_equidistant_ones(s: str) -> bool:
    """Check if all 1s in a binary string are equidistant."""
    indices = [i for i, char in enumerate(s) if char == '1']

    if len(indices) < 2:
        return True

    gaps = [indices[i + 1] - indices[i] for i in range(len(indices) - 1)]

    return len(set(gaps)) == 1


print(has_equidistant_ones("1001001"))  # True (gaps: 3, 3)
print(has_equidistant_ones("101001"))   # False (gaps: 2, 3)
print(has_equidistant_ones("10101"))    # True (gaps: 2, 2)
print(has_equidistant_ones("1"))        # True (single 1)
print(has_equidistant_ones("0000"))     # True (no 1s)

Output:

True
False
True
True
True

Using `zip` for Cleaner Gap Calculation

def has_equidistant_ones_zip(s: str) -> bool:
    """Check equidistant 1s using zip for gap calculation."""
    indices = [i for i, char in enumerate(s) if char == '1']

    if len(indices) < 2:
        return True

    gaps = [b - a for a, b in zip(indices, indices[1:])]

    return len(set(gaps)) == 1

Returning the Gap Value

Often you need to know the actual gap, not just whether they're equidistant:

def get_equidistant_gap(s: str) -> int | None:
    """
    Return the gap if 1s are equidistant, None otherwise.
    Returns 0 for strings with fewer than 2 ones.
    """
    indices = [i for i, char in enumerate(s) if char == '1']

    if len(indices) < 2:
        return 0

    first_gap = indices[1] - indices[0]

    for i in range(2, len(indices)):
        if indices[i] - indices[i - 1] != first_gap:
            return None

    return first_gap


print(get_equidistant_gap("1001001"))  # 3
print(get_equidistant_gap("101001"))   # None
print(get_equidistant_gap("10101"))    # 2

Early Exit Optimization

For long strings, exit as soon as a mismatch is found:

def has_equidistant_ones_fast(s: str) -> bool:
    """Optimized version with early exit."""
    indices = [i for i, char in enumerate(s) if char == '1']

    if len(indices) < 2:
        return True

    expected_gap = indices[1] - indices[0]

    for i in range(2, len(indices)):
        if indices[i] - indices[i - 1] != expected_gap:
            return False

    return True

Using NumPy for Large Data

When processing millions of bits, NumPy's vectorized operations are significantly faster:

import numpy as np


def has_equidistant_ones_numpy(s: str) -> bool:
    """Check equidistant 1s using NumPy (faster for large strings)."""
    arr = np.array(list(s), dtype=np.int8)

    indices = np.nonzero(arr)[0]

    if len(indices) < 2:
        return True

    gaps = np.diff(indices)

    return np.all(gaps == gaps[0])


print(has_equidistant_ones_numpy("1001001"))  # True

Working with Integers Instead of Strings

If you have an integer and want to check its binary representation:

def has_equidistant_ones(s: str) -> bool:
    """Check if all 1s in a binary string are equidistant."""
    indices = [i for i, char in enumerate(s) if char == '1']

    if len(indices) < 2:
        return True

    gaps = [indices[i + 1] - indices[i] for i in range(len(indices) - 1)]

    return len(set(gaps)) == 1

def int_has_equidistant_ones(n: int) -> bool:
    """Check if 1s in binary representation of n are equidistant."""
    if n <= 0:
        return True

    binary_str = bin(n)[2:]  # Remove '0b' prefix
    return has_equidistant_ones(binary_str)


print(int_has_equidistant_ones(73))   # 73 = 1001001 → True
print(int_has_equidistant_ones(41))   # 41 = 101001 → False

Output:

True
False

Finding Equidistant Patterns

Find all substrings where 1s are equidistant:

def get_equidistant_gap(s: str) -> int | None:
    """
    Return the gap if 1s are equidistant, None otherwise.
    Returns 0 for strings with fewer than 2 ones.
    """
    indices = [i for i, char in enumerate(s) if char == '1']

    if len(indices) < 2:
        return 0

    first_gap = indices[1] - indices[0]

    for i in range(2, len(indices)):
        if indices[i] - indices[i - 1] != first_gap:
            return None

    return first_gap


def has_equidistant_ones(s: str) -> bool:
    """Check if all 1s in a binary string are equidistant."""
    indices = [i for i, char in enumerate(s) if char == '1']

    if len(indices) < 2:
        return True

    gaps = [indices[i + 1] - indices[i] for i in range(len(indices) - 1)]

    return len(set(gaps)) == 1


def find_equidistant_substrings(s: str, min_ones: int = 3) -> list:
    """Find all substrings with equidistant 1s."""
    results = []
    n = len(s)

    for start in range(n):
        for end in range(start + min_ones, n + 1):
            substring = s[start:end]
            ones_count = substring.count('1')

            if ones_count >= min_ones and has_equidistant_ones(substring):
                gap = get_equidistant_gap(substring)
                results.append({
                    'substring': substring,
                    'start': start,
                    'end': end,
                    'ones': ones_count,
                    'gap': gap
                })

    return results


patterns = find_equidistant_substrings("10101001")
for p in patterns:
    print(p)