Norbert wrote:
> Hi, please help me solve this problem. It's something like that: given
> an array A[1...n] filled with different integers in range [1...n],
> find a missing number. The only operation which you can use is
> get_ith_bit_from_pos_n(i, n) = i'th bit of A[n]. This can be solved in
> O(n) time. But how?
Assuming:
1. the stuff about reading bit by bit is a pointless irritant.
2. it's OK to destroy the contents of A.
3. the entries of A can be set to zero.
4. O(1) aux space usage is OK.
for (scan = 1; scan <= N; scan++)
{
curr = A[scan];
if (curr != 0)
for ( ; ; )
{
next = A[curr];
if (next == 0)
break;
A[curr] = 0;
curr = next;
}
}
for (scan = 1; scan <= N; scan++)
if (A[scan] != 0)
return(scan);
// Else no number missing.
return(0);
The inner for loop would execute at most 2N times in total,
so the algorithm is O(N) .
--~--~---------~--~----~------------~-------~--~----~
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-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
