I was recently asked this question in an interview and I was wondering if any of you could help me find a better solution to this problem. The question goes like this:
There is a function foo which takes two arguments: an array "a" of type int and another int "b".
foo(int a, int b)
Now, we have to write an algorithm so that it returns true if the sum of any 2 elements in array a is equal to the integer b or else return false.
The simplest way is to iterate through each element in "a" and in another inner loop, add it to every other element in the array to see if the sum equals b or not but this algorithm would run in quadratic time.
Is there are more efficient way of solving this problem? I'm sure there is but just can't think of one right now.