Tuesday, May 11, 2010

Search two numbers from array to make a sum

You have a array of random numbers and you are given a number k. Find the 2 elements in the array which sum up to k.
e.g: If my array is {2,5,3,1,8,7,5,4} and k=6.
Then 2 numbers that sum up to 6 are 5 and 1.

step 1: sort the array //O(n.log(n))
arr=2,5,3,1,8,7,5,4 --> 1,2,3,4,5,5,7,8


step 2:

i=0, j=7

if a[i]+a[j]==K //done
if a[i]+a[j] > K //j--
if a[i]+a[j] < K //i++

repeat step2, till it reaches mid point //O(n)

No comments:

Post a Comment