Solving the array sum problem using iterators and testing for equality only

Question

While getting ready for interviews, I decided to code the classic "Find if there are two elements in an array that sum up to a given number" question using iterator logic, so that it can be generalized to other containers than vector.

Here's my function so far

// Search given container for two elements with given sum. 
// If two such elements exist, return true and the iterators 
// pointing to the elements. 
bool hasElementSum( int sum, const vector<int>& v, vector<int>::iterator& el1, vector<int>::iterator& el2 )
{
    bool ret = false;
    el1 = v.begin();
    el2 = v.end()-1;
    while ( el1 != el2 ) {
        if ( *el1 + *el2 == sum ) return true;
        ++el1;--el2;
    }
    return false;
}

This, of course, doesn't work, but I couldn't figure out a way to do it without using the condition while ( el1 >= el2 ). Various sources I looked advise against using omnly equality checking for iterators, to be able to generalize to all types of containers that support iterators.

Thanks!

Answer 1

Isn't this question usually asked with a sorted array ?
If not it has to work in O(n^2) complexity, and you will have to check all possible pairs.

Answer 2

foreach element1 in array
  foreach element2 in array + &element1
    if( element1 + element2 == sum )
      return true
return false

This is O(N^2), since you have to add each element to each of the other elements.

Answer 3

First of all, your algorithm is wrong unless you've somehow determined ahead of time that you only need to look at sums where one item is in the first half of the collection, and the other is in the second half of the collection.

If the input's not sorted, then @sbi's answer is about as good as it gets.

With a sorted, random-access input, you can start with the first element, and do a binary search (or interpolation search, etc.) to see if you can find the value that would have to go with that to produce the desired sum. Then you can try the second element, but when you do the binary search (or whatever) use the result from the previous search as the upper limit. Since your first element is larger than the previous one, the matching value to produce the correct sum must be less than or equal to what you found the last time around.

Answer 4

I propose the following method though did not analyze the order

Construct a binary search tree with all the elements of the vector, Then for each element

foreach(element = vec.begin to vec.end)
{
    if element == node.data, skip

    if the element + node.data == sum, return true

    if the element + node.data > sum, goto left child

    if the element + node.data < sum, goto right child
}

Not a perfect solution/algorithm, but something of this kind.

Answer 5

Sorry, I screwed this one up. What I meant to write was a sort followed by a linear passed, which is the typical answer given to this question, as ltsik pointed out in his comment to Jerry, i.e. something like

bool hasElementSum( int sum, const vector<int>& v, int* ind1, int* ind2 )
{

    *ind1 = 0; *ind2 = v.size()-1;

    std::sort( v.begin(), v.end() );

    while ( *ind1 <= *ind2 ) {
        int s = v[*ind1] + v[*ind2];
        if ( s > sum ) (*ind1)++;
        else if ( s < sum ) (*ind2)++;
        else return true
    }
    return false;
}

My question was how to write this using iterators without saying while (iter1 <= iter2 ) in order to be general, but I now see that doesn't make sense because this algorithm needs random access iterators anyway. Also, returning the indexes is meaningless since they refer to the sorted array and not the original one.