Assume that is a sorted array of integers, and x is also an integer. De

Assume that < A, n > is a sorted array of integers, and x is also an integer. De

ID: 3663487 • Letter: A

Question

Assume that < A, n > is a sorted array of integers, and x is also an integer. Design an algorithm that in (n) steps finds i and j such that A[i] + A[j] = x or establishes that such i and j do not exist.

Hint: you need to find i and j, and you may assume that i j. Start by checking a pair where i is smallest possible, and j is largest possible, i.e. (i, j) = (0, n 1) so let z = A[0] + A[n 1]; obviously it is very nice if z = x but you can also conclude something useful when z < x and when z > x.

EXTRA question: Design an algorithm that in (n 2 ) steps, and using (n 2 ) memory finds i, j, k, m such that A[i] + A[j] + A[k] + A[m] = x or establishes that this is not possible.

Explanation / Answer

This method works in O(n) time if range of numbers is known.
Let sum be the given sum and A[] be the array in which we need to find pair.

#include <stdio.h>

#define MAX 100000

void printPairs(int arr[], int arr_size, int sum)

{

int i, temp;

bool binMap[MAX] = {0}; /*initialize hash map as 0*/

for (i = 0; i < arr_size; i++)

{

temp = sum - arr[i];

if (temp >= 0 && binMap[temp] == 1)

printf("Pair with given sum %d is (%d, %d) ",

sum, arr[i], temp);

binMap[arr[i]] = 1;

}

/* Driver program to test above function */

int main()

{

int A[] = {1, 4, 45, 6, 10, 8};

int n = 16;

int arr_size = sizeof(A)/sizeof(A[0]);

printPairs(A, arr_size, n);

getchar();

return 0;

}