in arrange 1..n there are n different numbers. how can you fill A[1..n]
without any one of them?
2006/12/1, W Karas <[EMAIL PROTECTED]>:
>
>
> 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
