Guneesh, Thanks for the reply. I interpret ur answer as follows:
If N = say, 50 the two combinations are (1,7) and (5,5). Acc to you, first find sqrt(50) = 7 fill in 1,4,9,16,25,36,49 in an array. Then have min = 0, max = 6 and get all combinations in one pass over the array, right? So, the complexity would be O(n^0.5), right? Can you think of any solution making use of complex domain? Just curious to know... On Wed, Feb 13, 2013 at 10:28 PM, Guneesh Paul Singh <[email protected]>wrote: > Replace all elements of array by its square.and sort it > Now question is to find two nos in the array such that their sum is N. > For this take two pointers min and max > Initialize min to 0 and max to n-1(n-size of array) > 1.find the sum a[min]+a[max] > 2.if sum>N max=max-1 > if sum<N min=min+1 > if sum==N we have a sol > > Now in case of nonunique values all possible pairs must be displayed > eg for 2 2 3 3 N =5 > min=0,max 3 is a sol but u need to display all combination of 2 and 3 for > that i used tempmin=position till which we have a value a[min] and temp max > postion till which we have a value a[max] and display > all possible combinations. > > P.S. This was asked to me in Amazon > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- Regards, Shachindra A C -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
