yes, think about the logic working behind bucket sort. we assume in this problem, memory space is inf
all you need to do is put all numbers in its own "bucket" when a number was pushed into one bucket which had already been occupied, you have the duplicated number there. when you run to n-1 number, you know all the numbers so far are unique(coz duplication hadn't happened). by definition of the problem, you have only one duplicated number. therefore, the last number is duplicated. O(2(n-1)) > O(n) On Oct 5, 7:41 am, sourav <[email protected]> wrote: > You are given an array of positive numbers in which one number is > repeated. Rest all are present only once. Find the duplicate number in > linear or sub linear time. -- 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?hl=en.
