wrb wrote:
> in arrange 1..n there are n different numbers. how can you fill A[1..n]
> without any one of them?
That occurred to me as well, but I assumed that it must be allowed that
for A[i] == A[j], i != j because otherwise it would be impossible for
there
to be any missing numbers.
>
>
>
> 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) .
> >
> >
> > >
> >
>
> ------=_Part_50614_9096516.1164934509339
> Content-Type: text/html; charset=ISO-8859-1
> X-Google-AttachSize: 1801
>
> <div>in arrange 1..n there are n different numbers. how can you fill A[1..n]
> without any one of them?</div>
> <div><br><br> </div>
> <div><span class="gmail_quote">2006/12/1, W Karas <<a href="mailto:[EMAIL
> PROTECTED]">[EMAIL PROTECTED]</a>>:</span>
> <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px
> 0.8ex; BORDER-LEFT: #ccc 1px solid"><br>Norbert wrote:<br>> Hi, please help
> me solve this problem. It's something like that: given<br>> an array A[1...n]
> filled with different integers in range [1...n],
> <br>> find a missing number. The only operation which you can use is<br>>
> get_ith_bit_from_pos_n(i, n) = i'th bit of A[n]. This can be solved in<br>>
> O(n) time. But how?<br><br>Assuming:<br>1. the stuff about reading bit by
> bit is a pointless irritant.
> <br>2. it's OK to destroy the contents of A.<br>3. the entries of A can be
> set to zero.<br>4. O(1) aux space usage is OK.<br><br>for (scan = 1; scan <=
> N; scan++)<br>{<br> curr = A[scan];<br> if (curr != 0)<br> for ( ; ; )
> <br> {<br> next = A[curr];<br> if (next ==
> 0)<br> break;<br> A[curr] = 0;<br> curr =
> next;<br> }<br>}<br><br>for (scan = 1; scan <= N; scan++)<br>if
> (A[scan] != 0)<br>
> return(scan);<br><br>// Else no number missing.<br>return(0);<br><br>The
> inner for loop would execute at most 2N times in total,<br>so the algorithm
> is O(N) .<br><br><br>
> ------=_Part_50614_9096516.1164934509339--
sp; }<br>}<br><br>for (scan = 1; scan <= N; scan++)<br>if (A[scan] !=
0)<br>
> return(scan);<br><br>// Else no number
> missing.<br>return(0);<br><br>The inner for loop would execute at most 2N
> times in total,<br>so the algorithm is O(N) .<br><br><br>
> ------=_Part_50614_9096516.1164934509339--
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
