0

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

Edited by ashu2401: n/a

5
Contributors
10
Replies
11
Views
6 Years
Discussion Span
Last Post by arkoenig
0

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.

Edited by Momerath: n/a

0

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)

Edited by guyfrompluto: the code tags

0

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.

0

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.

Edited by guyfrompluto: n/a

0

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..

0

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.

0

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).

0

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.:)

0

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.