Find if summation of numbers from two lists is given number

Problem: Given two lists A & B define an algo, which will identify two numbers 'a' and 'b', such that a + b = x, where 'x' is the input.

2 comments:

Madhur Kumar Tanwani said...

Solution :
1.> Sort both lists
2.> Iterate over first list
3.> For each element (a) in the first list, find the difference (x-a), in the 2nd list
4.> If the difference is found return 'a' and 'x-a'.

Time complexity : O(n log n)

Madhur Kumar Tanwani said...

Similar problem for a single list :

http://inder-gnu.blogspot.com/2007/10/find-two-nos-in-array-whose-sum-x.html

 
Stats