-1

Can someone provide an O(n*log n) algorithm that accepts an array of length n which has elements in the range {1,2,3....n} as input and checks whether the array contains 2b = a+c ? I know how to do it in O(n * n) but I need to optimise it to O(n* log n).

RAM
  • 211
  • 1
  • 4
  • 14
  • What are a, b and c? elements in the set? – Pham Trung Feb 05 '18 at 08:33
  • Yes ,the elements in the input set which is a subset of {1,2,3,4....n} – RAM Feb 05 '18 at 08:34
  • 1
    What have you tried so far? Share your findings! Show us some code! – MrSmith42 Feb 05 '18 at 08:39
  • I got O(n * n) algorithm but I need it in O(n* log n) time. – RAM Feb 05 '18 at 08:40
  • I think you want the algorithm stack exchange, unless you plan on putting this into some sort of specific coding language. – G_V Feb 05 '18 at 08:55
  • 1
    What gives you the impression that there is a O(n* log n) solution? Is this HOMEWORK ? – MrSmith42 Feb 05 '18 at 09:17
  • O(1) is a subset of `O(n*log n)`. – greybeard Feb 05 '18 at 09:21
  • @greybeard: I agree. Do you have an O(1) algorithm to solve this? Would be a very suitable answer to the question. – MrSmith42 Feb 05 '18 at 09:33
  • Really an interesting problem. I can't figure out a solution, but a found it https://stackoverflow.com/questions/1560523/onlogn-algorithm-find-three-evenly-spaced-ones-within-binary-string/1579165#1579165 – llllllllll Feb 05 '18 at 09:39
  • Thanks @liliscent for giving the hint ,by the way this was a question which appeared in my exam yesterday for which the syllabus was FFT,Divide and conquer.I wasn't able to figure it out as I was thinking it to solve it in Divide and conquer way.I didn't thought it would involve FFT.Now I will proceed with the link given. – RAM Feb 05 '18 at 09:57
  • If you don't exclude a=b=c, I guess there is a (low) limit to n above which such a triple *always* exists. – greybeard Feb 05 '18 at 18:41

1 Answers1

3

Please don't laugh at such questions if you don't know the answer.I figured out the answer myself by the link posted in the comments. Source:O(nlogn) Algorithm - Find three evenly spaced ones within binary string

The solution is, Let L = [1, 2, 4, 5, 8].

  1. The problem is now to find an arithmetic progression of length 3 in L, i.e. to find distinct a, b, c in L such that b-a = c-b, or equivalently a+c=2b. For the example above, we want to find the progression (2, 5, 8).

Make a polynomial p with terms xk for each k in L. For the example above, we make the polynomial p(x) = (x + x2 + x4 + x5+x8). This step is O(n).

Find the polynomial q = p2, using the Fast Fourier Transform. For the example above, we get the polynomial q(x) = x16 + 2x13 + 2x12 + 3x10 + 4x9 + x8 + 2x7 + 4x6 + 2x5 + x4 + 2x3 + x2. This step is O(n log n).

Ignore all terms except those corresponding to x2k for some k in L. For the example above, we get the terms x16, 3x10, x8, x4, x2. This step is O(n), if you choose to do it at all.

Here's the crucial point: the coefficient of any x2b for b in L is precisely the number of pairs (a,c) in L such that a+c=2b. [CLRS, Ex. 30.1-7] One such pair is (b,b) always (so the coefficient is at least 1), but if there exists any other pair (a,c), then the coefficient is at least 3, from (a,c) and (c,a). For the example above, we have the coefficient of x10 to be 3 precisely because of the AP (2,5,8). (These coefficients x2b will always be odd numbers, for the reasons above. And all other coefficients in q will always be even.)

So the total time complexity won't cross O(n* logn).

Thankyou.

RAM
  • 211
  • 1
  • 4
  • 14