How to Check if 1s are Equidistant in a Binary String 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:

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

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

    # Need at least 2 ones to measure a distance
    if len(indices) < 2:
        return True

    # Calculate gaps between consecutive indices
    gaps = [indices[i + 1] - indices[i] for i in range(len(indices) - 1)]

    # All gaps should be equal (set will have only one element)
    return len(set(gaps)) == 1


# Test cases
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

    # Pair consecutive elements: (0,3), (3,6), etc.
    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)."""
    # Convert string to integer array
    arr = np.array(list(s), dtype=np.int8)

    # Get indices where value is 1
    indices = np.nonzero(arr)[0]

    if len(indices) < 2:
        return True

    # Calculate differences between consecutive indices
    gaps = np.diff(indices)

    # Check if all gaps equal the first gap
    return np.all(gaps == gaps[0])


# Test
print(has_equidistant_ones_numpy("1001001"))  # True

Performance Note

NumPy has overhead for small strings. Use it only when processing strings with thousands of characters or when batch processing many strings.

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."""
    # Find all positions of '1'
    indices = [i for i, char in enumerate(s) if char == '1']

    # Need at least 2 ones to measure a distance
    if len(indices) < 2:
        return True

    # Calculate gaps between consecutive indices
    gaps = [indices[i + 1] - indices[i] for i in range(len(indices) - 1)]

    # All gaps should be equal (set will have only one element)
    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."""
    # Find all positions of '1'
    indices = [i for i, char in enumerate(s) if char == '1']

    # Need at least 2 ones to measure a distance
    if len(indices) < 2:
        return True

    # Calculate gaps between consecutive indices
    gaps = [indices[i + 1] - indices[i] for i in range(len(indices) - 1)]

    # All gaps should be equal (set will have only one element)
    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


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

Output:

{'substring': '10101', 'start': 0, 'end': 5, 'ones': 3, 'gap': 2}
{'substring': '101010', 'start': 0, 'end': 6, 'ones': 3, 'gap': 2}
{'substring': '1010100', 'start': 0, 'end': 7, 'ones': 3, 'gap': 2}

Edge Cases

Input	Result	Reason
""	True	No 1s to compare
"0000"	True	No 1s to compare
"1"	True	Single 1, no gap needed
"11"	True	Gap of 1
"1001001"	True	Gaps: 3, 3
"101001"	False	Gaps: 2, 3

Method Comparison

Method	Time	Space	Best For
List + Set	O(n)	O(k)	General use
Early Exit	O(n)	O(k)	When false cases are common
NumPy	O(n)	O(n)	Large strings, batch processing

n = string length, k = number of 1s

Summary

• Collect indices of all 1s using list comprehension with enumerate().
• Calculate gaps using zip(indices, indices[1:]) or np.diff().
• Check uniformity with len(set(gaps)) == 1 or compare all gaps to the first.
• Use early exit for better average-case performance.
• Consider NumPy only for very large datasets.