my idea is like this: 1/ find a number k in the array where k-z is minimum. 2/ then arrange the array in such a way that array[1...r] contains the numbers less than z, a[r] contains the k , a[r+1, .. n] contains the numbers greater than z. ( like one iteration of quick sort, if i remember quciksort properly)
3/ now moving from r to 1 one head and r+1 to n another head, one can find the possible solutions of x+y =z. the whole idea is using the "one iteration of quick sort'. thanks, sudhakar Paranthaman Saravanan wrote: > hey vijay finding the two numbers if the array is sorted is known try to > find for if the array is not sorted.... > any one can help me in finding this > > > On 12/19/05, Vijay Venkat Raghavan N <[EMAIL PROTECTED]> wrote: > > > > Hi, > > > > I guess this has already been discuss in this forum before. Anyways let me > > give my algo here. Let us assume that the array is sorted in ascending order > > WLOG. > > > > let low=1 and high=n index the first and last elements > > while(low<high) > > { > > if a[low]+a[high] == z, done, so break off > > if a[low]+a[high]<z need to increase sum, so low++; > > 3rd case, u need to decrease, so high-- > > } > > > > hope this helps. > > > > -Vijay > > > > On 12/19/05, Uppala Babu <[EMAIL PROTECTED]> wrote: > > > > > > Hash map takes extra space if you want O(1) search.. > > > Otherwise .. it takes time... any another solution... > > > > > > in O(n) time with no extra space.. ;-) > > > > > > On 12/19/05, Hemanth < [EMAIL PROTECTED]> wrote: > > > > > > > > > > > > This answer is something like a bit vector based one. > > > > > > > > Assume that the array is int[] num. > > > > for(int i = 0; i < num.length; i++) > > > > { > > > > int otherNum = z - num[i]; > > > > > > > > // Search in a hashmap we maintain for 'otherNum' > > > > // if 'otherNum' is present, then we are done > > > > // else add 'num[i]' to the hashmap and proceed > > > > // to the next iteration. > > > > } > > > > > > > > > > > > > > > > -- > Arise awoke stop not till the goal is reached