176

I had this question on an Algorithms test yesterday, and I can't figure out the answer. It is driving me absolutely crazy, because it was worth about 40 points. I figure that most of the class didn't solve it correctly, because I haven't come up with a solution in the past 24 hours.

Given a arbitrary binary string of length n, find three evenly spaced ones within the string if they exist. Write an algorithm which solves this in O(n * log(n)) time.

So strings like these have three ones that are "evenly spaced": 11100000, 0100100100

edit: It is a random number, so it should be able to work for any number. The examples I gave were to illustrate the "evenly spaced" property. So 1001011 is a valid number. With 1, 4, and 7 being ones that are evenly spaced.

Improve this question
28
  • 4
    Is the following possible: 10011010000 ? It has three 1s (first, second, forth) evenly spaced out, but there are also additional 1s. Commented Oct 13, 2009 at 14:27
  • 5
    Robert, you need to get your professor to give you the answer for this and post it here. This problem is driving me up the wall. I can figure out how to do it in n^2 but not n*log(n). Commented Oct 14, 2009 at 1:29
  • 3
    Hmm I spent a long while trying to figure this out too, haven't yet come across a good answer. Perhaps you misunderstood the question? For example, if the question asks, find an algorithm that runs in O(n log n ) that determines the position of an evenly spaced sequence of spacing k, in a much larger sequence, this could be easily done using the fast fourier transform. Commented Oct 14, 2009 at 2:47
  • 2
    if your prof gives a solution please post it as an answer. Commented Oct 14, 2009 at 2:49
  • 5
    Considering the fact that Klaus Roth got a Fields Medal 1958 for (among other things) proving that for each density d>0 there is a natural number N such that each subset of {1,...,N} with at least d*N elements contains an arithmetic progression of length 3, I'm not surprised that until now nobody found a convincing algorithm for the problem yet. See also en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem Commented Oct 16, 2009 at 20:56

31 Answers 31

Reset to default
1
2
-7

This is possible to solve in linear time O(n)

  1. start at beginning, and wait for first 1
  2. Start counting zeros.
  3. When you hit 1 store number of counted zeros (valid number is also 0) NumberOfZeros -> PrevZeros
  4. Start counting zeros.

  5. When you hit 1 check NumberOfZeros == PrevZeros

    If true return counter

    else NumberOfZeros -> prev_zeros and goto 4

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

@ralu, this is what I did in my answer. The problem is a lot more complicated because 1 can also be a spacer.
i didn not think of that, but if whole stackowerflow did not crack this in in 2 days, how would somebody solve this problem in 1hour during exam?
Best idea I can think of now, would be using property that desity of ones is at most n/ln(n) (phi funtcion from prime density) if there is no solution. That mean that this can be solved in n^2/log(n) time.
This can be easily solved in nlog(n) if can be proven that worst density is klog(n) in long run.
1
2

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.