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 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 -~----------~----~----~----~------~----~------~--~---