Introduction

The problem is to find indices i, j, and k in a binary string such that all three positions contain 1 and the spacing is even, meaning j - i = k - j. The fastest practical way to solve this is often simpler than the title suggests: collect the indices of all 1 bits and use a set for midpoint checks, which gives linear-time behavior in most languages.

Convert the String Into Indices of Ones

The first step is to record where the 1 characters appear.

1def one_positions(bits: str) -> list[int]:
2    return [i for i, ch in enumerate(bits) if ch == "1"]
3
4
5print(one_positions("100101001"))  # [0, 3, 5, 8]

Once you have this list, the question becomes geometric: do any three recorded positions form an arithmetic progression?

Check Midpoints Efficiently

If positions a and c are the endpoints, then the middle point must be (a + c) / 2. That midpoint only works if the sum is even and the midpoint position also contains a 1.

1def find_three_evenly_spaced_ones(bits: str):
2    positions = one_positions(bits)
3    ones = set(positions)
4
5    for left_index in range(len(positions)):
6        for right_index in range(left_index + 1, len(positions)):
7            a = positions[left_index]
8            c = positions[right_index]
9
10            total = a + c
11            if total % 2 != 0:
12                continue
13
14            b = total // 2
15            if b in ones:
16                return a, b, c
17
18    return None
19
20
21print(find_three_evenly_spaced_ones("100101001"))

This is easy to explain and usually good enough unless the number of ones is extremely large.

Why the Arithmetic Progression View Matters

Three evenly spaced indices are just a length-three arithmetic progression. Reframing the problem this way makes the midpoint test obvious and prevents wasted work checking unrelated triples.

That shift in viewpoint is often what interviewers or contest problems are really testing.

About the Claimed O(n log n) Goal

If the input is already a binary string in index order, the list of one-positions is naturally sorted. That means you can often do better than O(n log n) in practice by using a hash set for midpoint membership checks.

The exact complexity depends on:

• 'n, the string length'
• 'm, the number of ones'

The midpoint-search version above is O(m^2) after preprocessing, which is excellent when ones are sparse but not ideal when the string is dense. More advanced approaches exist, but for most real discussions the important part is to choose the right representation first.

Handle Obvious Early Exits

Before doing any heavier work, check simple conditions:

• fewer than three ones means failure immediately
• strings shorter than three also fail immediately

Small early exits make the implementation cleaner and avoid wasted loops.

Common Pitfalls

• Checking all triples directly and drifting into cubic time.
• Forgetting that the midpoint must land on an integer index.
• Mixing string indices with counts of ones and getting the wrong spacing.
• Over-focusing on a target complexity label before choosing a clean representation.
• Ignoring the difference between string length and number of ones.

Summary

• The problem is equivalent to finding a length-three arithmetic progression among the positions of 1 bits.
• Converting the string to indices of ones simplifies the problem immediately.
• Midpoint checking is the core observation: the middle index must be the average of the endpoints.
• Early exits help when the string has too few ones.
• A clean representation usually matters more than forcing a complicated algorithm too early.