Question

Given an array of integers, find two numbers such that they add up to a specific target number.

Answer 1

hasArrayTwoCandidates (A[], ar_size, sum) 1) Sort the array in non-decreasing order. 2) Initialize two index variables to find the candidate elements in the sorted array. (a) Initialize first to the leftmost index: l = 0 (b) Initialize second the rightmost index: r = ar_size-1 3) Loop while l < r. (a) If (A[l] + A[r] == sum) then return 1 (b) Else if( A[l] + A[r] < sum ) then l++ (c) Else r-- 4) No candidates in whole array - return 0Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.

Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.

Example :

Let Array be {1, 4, 45, 6, 10, -8} and sum to find be 16

Sort the array

A = {-8, 1, 4, 6, 10, 45}

We will increment’l’ when sum of pair is less than required sum and decrement ‘r’ when sum of pair is more than required sum.

This is because when sum is less than required then we need to get the number which could increase our sum of pair so we move from left to right(also array is sorted)thus “l++” and vice versa.

Initialize l = 0, r = 5

A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 4

A[l] + A[r] ( -8 + 10) increment l. Now l = 1

A[l] + A[r] ( 1 + 10) increment l. Now l = 2

A[l] + A[r] ( 4 + 10) increment l. Now l = 3

A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)

Note: If there are more than one pair having the given sum then this algorithm reports only one. Can be easily extended for this though.