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

APPROACH 3

Having seen O(n^2) and O( n \log n) 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 O(n) 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 O(n).

——–

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 O(n).

Also, the space complexity is O(1) 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;

}

}

———–


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: