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 <[email protected]>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 [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
-~----------~----~----~----~------~----~------~--~---
