1

I had an exam in algorithms today and we had the following task. I didn't really solve it, but know I am really interested how it works.

Task: We have a bit vector s and we want to know if there are triples in the vector, so if 1 stands in Index i, j, k then k-j = j-i

Example: [0,1,0,0,1,0,0,1], i = 1 , j = 4, k = 7

I have solved the problem for an algorithm in O(n^2), so we have two loops, in the outer loop we search for the first 1, in the inner loop we search for the index of j and then we calculate the index of k with i and j and check, if on the index of k is a 1 too.

But it should be an algorithm in O(nlog(n)). We had the hint, that we can use x^i x^k = x^k x^i for the algorithm in O(nlog(n)). Has anyone an idea, how to solve the problem in O(nlog(n))?

user650708
  • 55
  • 4
  • How can you tell it should be solved using `divide-and-conquer`? I think there is a nice solution here using `FFT` but I need to know if you have learned this in your course. – Yonlif Mar 05 '19 at 20:18
  • Ok I have found a question that is just like yours, there is the [answer](https://stackoverflow.com/a/1585303/7501501), it use `FFT` indeed and no one will explain it better than this. I think you should remove the question since it's a duplicate. – Yonlif Mar 05 '19 at 20:25
  • Is there a solution without FFT? – user650708 Mar 05 '19 at 20:39

0 Answers0