Arrays in C++ : Finding appropriate pairs in an array – 1

We are given an array A of ints, say of length n, and an integer target. Our task is to output all pairs of elements in A which add up to target.

For example, if target = 90, and the array A = {40, 20, 30, 50, 35, 60}, the output should be {40, 50}, {30, 60}. (The output is allowed to be in any order we like as long as all relevant pairs appear in it exactly once.)

————

APPROACH 1

A direct method could be to check all possible pairs of elements in A. For each pair that satisfies the required condition, we output that pair. For an array of length n, there are n \choose 2 possible pairs. The processing time for each pair is O(1). Hence, the running time is O(n^2). Also, the memory requirement is O(1).

——

In pseudo code, we could write it as follows:

For i going from 0 to n-1

For j going from i+1 to n-1

If A[i] + A[j] == target

Print {A[i], A[j]}

——

Transcribing that in C++, we would get:-

——

#include <iostream.h>

// function f takes an int array A, length n of A, and an int target.

//It prints all pairs of elements in A that sum to target.

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

{

for ( int i = 0; i < n-1; i++)

for (int j = i+1; j < n-1; j++)

if (A[i] + A[j] == target)

cout << endl << “{ ” << A[i] << “, ” << A[j] << ” }”;

}

———–

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: