Here is a program that might be bad but is theoretically O(n) for
unsigned integers. You can just cast signed integers to unsiged ones
and then cast the result back to a signed integer to get it to work
with signed integers.
#include <iostream>
#include <list>
using namespace std;
//consider the recursion tree, at each level of the tree
//each number will show up at most one time. Since there are
//always a constant number of levels in the tree
//(sizeof(unsigned int) * 8 - 1) this function runs in O(n)
unsigned int findDup(list<unsigned int> &l, unsigned mask)
{
if(l.size() < 2)
return 0;
else if(l.size() == 2 && mask == 0)
return l.front();
list<unsigned int> lo, lz;
for(list<unsigned int>::iterator it = l.begin(); it != l.end(); it++)
if(*it & mask)
lo.push_back(*it);
else
lz.push_back(*it);
mask = mask >> 1;
return findDup(lo, mask) + findDup(lz, mask);
}
int main()
{
unsigned int nums[] = {3, 77, 28, 89, 2777, 431, 24, 1, 999999, 99998,
78, 88, 2, 3};
list<unsigned int> l(nums, nums + sizeof(nums) / sizeof(unsigned
int));
cout << findDup(l, 1 << (sizeof(unsigned int) * 8 - 1)) << endl;
cin.get();
return 0;
}
shashi_genius wrote:
> There are n numbers with all (n-1) unique numbers, except for one which
> is repeating.
> Find out the repeating number in O(n) complexity.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
