sorry, i thought the element that is repeated is of the form 2^i. :D
On Sun, Aug 9, 2009 at 6:14 PM, Siddharth S <mitsiddha...@gmail.com> wrote: > assuming the numbers are n-bit numbers, > 1. have an array, "arr", of n elements, initialize all elements with 0. > 2. traverse the "input" array > 3. if input[i] is a power of 2, > arr[ lg(input[i]) ] ++; // where lg is logarithm to the base 2. > 4. after traversing input array, see if any element in "arr" array is 2. > 5. if so, let arr[i] be equal to 2. Then the element 2^i has appeared 2 > times. > > the method mentioned above is similar to hashing, which hashes powers of 2 > to an integer. > also, finding if a number is a power of 2 can be done in O(1) time. > so the above algo runs in O(n) time. > space complexity : O( lg(k) ), where the input numbers are k-bit numbers. > > > > On Sun, Aug 9, 2009 at 5:59 PM, Vikram Sridar > <vikramsridar...@gmail.com>wrote: > >> Sorting will tkae atleast a nlog(n)... this could be done in 0(n) if we >> hash.. worst case that is >> >> >> >> >> > --~--~---------~--~----~------------~-------~--~----~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
