find the posiible sums using brute force.then apply this algo
*function* findFirstK(list, left, right, k)
*if* right > left
select pivotIndex between left and right
pivotNewIndex := partition(list, left, right, pivotIndex)
*if* pivotNewIndex > k *// new condition*
findFirstK(list, left, pivotNewIndex-1, k)
*if* pivotNewIndex < k
findFirstK(list, pivotNewIndex+1, right, k)
where k is the smallest number u want to find out .here k is 8
On Fri, Sep 4, 2009 at 10:33 PM, ankur aggarwal <[email protected]>wrote:
> Find nth smallest inO(n) Given two arrays of length n in sorted order
> X[n] & Y[n].
> Now make another array Z[n^2]={such that z belongs to X+Y}.
> AS all possible sum of x+y is there in Z. You have to give the nth smallest
> no of Z in O(n) time.
> Space complexity : No bound on it. But try to optimize it if possible.
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
