Algorithm problem

[ashu2401]

Hi,

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.

Thanks,
Ash

[Momerath]

This is how I'd do it in C#:

Boolean foo(int[] a, int b) {
    Boolean result = false;
    Dictionary<int, Boolean> c = new Dictionary<int,Boolean>();

    for (int i = 0; i < a.Length; i++) {
        if (c.ContainsKey(b-a[i])) {
            result = true;
            break;
        } else {
            c.Add(a[i], true);
        }
    }

    return result;
}

Since Dictionary uses a hash to index, the ContainsKey method approaches a O(1) operation. This just leaves the loop going through the array making it an O(n) operation.

This does assume that all the numbers are unique, if not, you'd add a another call to ContainsKey() before you add the current value to the dictionary.

Any form of hash indexing will work, whatever language you choose.

[guyfrompluto]

Here is one in python hope it helps:

def sumOfNumbers(lst,num):
    temp=0
    while temp<len(lst):
        for i in range(0,len(lst)):
            if i==temp:
                continue
            if lst[temp]+lst[i]==num:
                return True
        temp=temp+1
    return False

print sumOfNumbers([1,2,3,4,5,6],3)

[Momerath]

Here is one in python hope it helps:

def sumOfNumbers(lst,num):
    temp=0
    while temp<len(lst):
        for i in range(0,len(lst)):
            if i==temp:
                continue
            if lst[temp]+lst[i]==num:
                return True
        temp=temp+1
    return False

print sumOfNumbers([1,2,3,4,5,6],3)

While it is a solution, it's no faster than the one the original poster discussed. Since you have a loop in a loop, you are looking at O(n^2) time.

[guyfrompluto]

While it is a solution, it's no faster than the one the original poster discussed. Since you have a loop in a loop, you are looking at O(n^2) time.

I am a newbie to programming so couldn't figure out a more efficient way to do it. Did it in python because I don't understand most of the above program in C# and assume a lot of others newbies don't either, and learning the language is not an option.

[techie1991]

If this was an interview question, you could have assumed the array to be sorted. (I did assume many things in my interviews and cleared most of the rounds).
Now, if the array is sorted, use a for loop with a search algorithm (binary search). The worst case would come down to O(n*logn).
A sort can also be performed in the starting, if the array is not assumed to be sorted. Use quicksort with average performance of O(n*logn) so that the overall complexity remains O(n*logn).
Hope this answers you a bit..

[arkoenig]

If the array is sorted, the problem is easy to solve in O(n).

Start with a pair of pointers (or indices) at opposite ends of the array. Step one of the pointers through the array one element at a time. For each element, step the other pointer backward through the array from its current position until the sum of the two elements is <= the value you're seeking. If the sum is equal, you've found two elements with the desired sum; if it goes from being greater than the sought value to being less than it, then you can continue stepping the first pointer.

[techie1991]

Absolutely...So this proves that the question can easily be solved in less than O(n^2). As said before, Even if the array is not sorted, we can sort it using any of the many available algorithms to bring down the complexity to atleast O(n*logn).

[Momerath]

You should read my first post again. Using hashtables you can solve this in O(n) time, no need to sort.

[techie1991]

Ok, that was also a really good method, but I have never myself implemented hash tables in C/C++ (except dictionaries in python). So, I could not understand at first look the ContainsKey() function of C# you used.:$
Now, I hope the post is marked "solved" cause I don't think that the algorithm complexity can go any way lower than this.:)

[arkoenig]

Also... implementing a hash table that works reliably in O(1) time for any number of entries is not exactly a trivial problem.