you can do it O(n) time if the input array is sorted. Find the min and max value of the array and then decide how many number can be eliminated based if they are greater than X.
This problem get complecated if we consider the integers are +ve as well as -Ve intergers in an array. But any way sorting take minimum of O(nlogn), so I dont think it can be done in just O(n). Thank You, Mayur On Nov 19, 3:19 pm, "Manish Garg" <[EMAIL PROTECTED]> wrote: > can find in O(n) if array is sorted.... > > On Nov 18, 2007 9:13 AM, dor <[EMAIL PROTECTED]> wrote: > > > > > You can do it in O(n log(n)) (without extra space). If you can afford > > O(T) extra space (where T is the largest number in the array, in > > absolute value), you can do it in O(n). > > > On Nov 17, 3:42 pm, geekko <[EMAIL PROTECTED]> wrote: > > > Suppose that you have an array of integers. Given a number X are there > > > any two numbers in the array in which their summation is equal to the > > > X? Can you find a solution in O(n)? > > -- > With Best Regards... > ----------- > Manish --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
