# Arrays in C++ – Finding appropriate pairs in an array – 3

March 8, 2011 Leave a comment

**APPROACH 3 **

Having seen and algorithms for this problem, the natural question to ask is whether we can do better than that.

Firstly, we observe that to output *all *pairs that sum to target, we would need to access all elements of the array. That gives a lower bound of for any algorithm that we may think of.

So, the question is whether we can actually achieve that lower bound and devise an algorithm with a time complexity of .

——–

To simplify our task let us assume that the array A only contains integers in the range 0 – 99, and that A contains only distinct elements.

For example, A = { 10, 20, 70, 40, 65, 55} and target = 75.

Now, for element 10, we would like to see if 65 is contained in A. Since the ints are from a given fixed range : 0-99, we can construct a lookup table of size 100, containing the counts of the number of time each corresponding int appears in A.

If the lookup table is called L, L[i] would contain the count of the integer i.

Thus, when processing element 10, we would simply check if L[65] is 1. This takes O(1) time.

Similarly, we would lookup some values corresponding to each of the other elements in A. Hence, the total time complexity is .

Also, the space complexity is since the size of L is constant.

———–

In pseudocode form, the above method would look like this:-

Create int array L of size 100. //we could as well use a boolean array, and indeed that would save memory.

Initialize L to all zeros.

For i going from 0 to n-1:

L [ A[i] ] ++; //increment count of element A[i].

//now print the pairs.

For i going from 0 to n-1:

If A[ i ] < (target – A [ i ] )// We need this to prevent a pair twice (e.g. as {10, 25} and {25,10} ).

If ( L [target – A[i] ] == 1 )

Print A[i], target – A[i].

————

We could code it in C++ like this:

**#include <iostream.h> **

**void f (int *A, int n, int target) **

**{**

**int L [100] = {0}; **

**for ( int i = 0; i < n ; i++) **

**L [ A[i] ] ++; **

**for ( i =0 ; i < n ; i++) **

**{**

**if ( A[i] < target – A[i]) **

**if ( L [target – A[i] ] == 1 ) **

**cout << A[i] << ” and ” << target – A[i] <<endl;
**

**}
**

**}**

**———–**