Question

Given unsorted array and a number k. Find 2 numbers such that sum is k.

Answer 1

Time 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.