Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Determine if A+B=C exists in an array of n integers

Tags:

This is a problem a friend of mine received as his homework (in algorithm and data structure class). He asked me about this. However, I can't solve it and have been thinking about it for some time during the last several days.

There are n random integers in the range [0, 231-1] (there may be duplicates. Determine if 3 numbers of these numbers satisfy A + B = C.

I first came up with a naive algorithm that's O(n2log n). I then came up with an algorithm that's O(n2). Here is the pseudo code:

sort(a); // non-descending
for (i = 0; i < n; i++) {
  j = i; k = i + 1;
  while (j < n && k < n) {
    if (a[i] + a[j] == a[k])
      return true;
    else if (a[i] + a[k] < a[j])
      k++;
    else
      j++;
  }
}
return false;

However, the problem states that 1 < n <= 106. I believe O(n2) is too slow. My solution doesn't make use of the randomness. However, I'm not sure if this is an important part of the problem.


Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!