1

Given an unsorted array A[1...n].Write an algorithm that returns true if there are three elements A[i], A[j], A[k] in A so that A[i]+ A[j] = A[k], otherwise the algorithm must return false (note that may be that A[i] = A[j] and it is legal). Needed time is O(n^2). I come up with an algorithm that works in O(n^2 * log(n)). My algorithm sorts the Array and then for each couple of two elements x,y uses binary search to find whether there is an element x+y. Is there a faster solution that takes O(n^2)?

Lev
  • 43
  • 4
  • I want to reach a worst-case O(n^2). So solutions with hash tables or other probabilistic data structures don't help – Lev Nov 08 '18 at 15:09
  • do you know, if such solution actually exists or not? Also is this task for high school or university? – libik Nov 08 '18 at 15:13
  • I heard about this problem in my University and there is a faster worst case solution. I can't come up with such one. – Lev Nov 08 '18 at 15:18
  • Are there any constraints on the input? For example the range of possible values... – Nelfeal Nov 08 '18 at 15:19
  • input - real numbers – Lev Nov 08 '18 at 15:19

2 Answers2

3

You could sort the array first - O(nlogn)

Then it boils down to finding two sum for A[k] among the elements A[0] .. A[k-1] for any element A[k]

The two sum for a sorted array can be found in O(n) with two pointer technique like:

boolean searchSum( int k, int[] A ) {
      if ( k > A.length - 1 || k < 2 ) return false;
      i = 0, j = k-1

      while ( i < j ) { 

            if (A[i] + A[j] == A[k]) 
                return true; 
            else if (A[i] + A[j] < A[k]) 
                i++; 
            else
                j--; 
      } 

      return false; 
}

for each k it is O(k-1) and overall the complexity should be O(n^2).

you could call searchSum like:

boolean myMethod( int[] A ) {

   sort(A);
   for ( int i = A.length - 1; i >= 2; i-- ) {
      if ( searchSum( i, A ) ) {
        return true;
      }
   }

   return false;
}
SomeDude
  • 13,876
  • 5
  • 21
  • 44
  • @libik seriously ? the value k supposed to be an index in the array. The method is really just a kind of prototype of how the problem can be solved, ofcourse I can break any method with meaningless input. – SomeDude Nov 08 '18 at 15:45
1

You could create a hash table of the elements of A which had O(1) lookup, and use it for your searches for x+y.

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
  • Hash table actually does not have O(1) lookup, its called pseudo-constant as this behaviour works only for limited amount of numbers. If you keep adding more and more numbers, it will start to grow to O(n) – libik Nov 08 '18 at 15:04
  • Thats also one of the reason why most databases usually using Balanced Trees with `log (n)` lookup for indexes and not the hash tables. – libik Nov 08 '18 at 15:06
  • In this way, I improve an average time. Is it possible to get the worst case time O(n^2)? – Lev Nov 08 '18 at 15:06
  • @Lev - you will not, hash tables have real comlexity of `O(n)` for lookups. (in terms of complexity, we talk about what is the complexity for unlimited amount of numbers) – libik Nov 08 '18 at 15:09
  • https://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete – libik Nov 08 '18 at 15:10
  • @libik Yes, so hash tables give O(n^3) worst case. It is a slow worst case solution – Lev Nov 08 '18 at 15:12
  • 2
    @libik what you say is true in general, for a generic hash table, and an unlimited input. But here the size of the input is given, so we will not be "keep adding more and more numbers", we have just `n` of them. So we allocate a hash table just once, no need to rehash. Therefore this solution with a hash table in both average and worst cases will be `O(n)`. – Andriy Berestovskyy Nov 08 '18 at 16:47