Algorithm to find the pair of numbers in an integer array whoes sum are equal

Question

Algorithm to find the pair of numbers in an integer array whoes sum are equal. ex {1 2 3 4 6}

here{3 2} { 4 1} should be the output, because the sum is 3+2=5, 4+1=5.

Here the main thing is the complexity shld be O(n). Please help me if we find any solutions for this?

Answer 1

Are you sure that the problem is solvable at all in O(n)?

Imagine the case when the input sequence is just {0, 0, 0, 0, 0, 0, ..., 0}. Here every two pairs satisfy the condition. Just listing all the pairs is already at least O(n^2).

Answer 2

I think it's possible:

you need a second array tmp = {} with the length of sum.

sum = 5
array = {1,2,3,4,6}
for every i in array{
    if i>=sum:
        continue
    if tmp[i] != 0 {
        output {i,(sum-i)}
        tmp[i] = 0
        continue
    }

    tmp[sum-i] := i
}

that's it. so simple and with O(n)

cons:

1. it won't find a pair like {5,0}, therefore you have to use real Integer-Objects to check at line 6 against NULL and assign NULL in line 8,
2. pairs with a negative number won't work.