puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Darius on 10 Jun 2005 00:39 ok here is a puzzle. there is an integer array whose length is odd, and all the numbers in the array appear exactly two times except one. Find the number in O(n) time. Try to do it without using any other data structure.
From: Emlyn Corrin on 10 Jun 2005 05:06 Darius wrote: > ok here is a puzzle. > there is an integer array whose length is odd, and all the numbers in > the array appear exactly two times except one. Find the number in O(n) > time. Try to do it without using any other data structure. > hint: xor
From: spinoza1111 on 10 Jun 2005 13:02 Darius wrote: > ok here is a puzzle. > there is an integer array whose length is odd, and all the numbers in > the array appear exactly two times except one. Find the number in O(n) > time. Try to do it without using any other data structure. Consider that if you choose a random number or the midpoint from the array and search (in a single loop) in both directions before and after that number for its unique mate, you will either discover that it is the unique number U (when your search ends "unsuccessfully") or else you will have a very interesting data structure: a group of THREE array segments a[0]..a[i], a[i+2]..a[i+j+2], a[i+j+4]..a[arraySize-1] when a[i+1] = a[i+j+3]. I'll assume you can DELETE elements. DELETE a[i+1] and a[i+j+3]. Choose the midpoint of the remaining elements and repeat...until you have one element in the array. In the worst case this will be U, but usually you will find U before you remove all entries except U. Do while arraySize >= 2 i = floor(arraySize/2) j = i-1, k = i+1 Do while j >= 0 or k < arraySize if j>=0 and a[i]=a[j] { L = j, exit do } if k<arraySize and a[i]=a[k] { L = k, exit do } decrement j, increment k End do If j < 0 and k > arraySize return i delete(i), delete(L) // Changes arraySize End Do As long as DELETE is an atomic and fast operation this algorithm is close to O(n) because the array gets smaller by two entries in the worst case through its major loop, and in the worst case for the inner loop (where the inner loop must search the entire array in both directions) the algorithm is finished by definition. The major flaw in this algorithm is its blithe assumption that DELETE is atomic and fast. As long as we're free to represent the array as a collection in a modern language that supports collections this isn't a problem. As long as the collection delete uses a bidirectional linked list delete is fast. Or, the array can be represented as a bidirectional linked list. If it is provided as an array of adjacent entries it can be copied to a linked list in O(n) time making the time close to O(n) by a constant factor. But suppose the array is a classic array, and delete involves moving elements. Each bidirectional search will still partition the array as above. Select the midpoint of the middle partition, or the last entry of the first partition (if the middle partition is empty) or the midpoint of the last partition (if the first and middle partitions are empty where a[0]=a[1]. Repeat the search. You will unnecessarily examine previously found pairs of numbers. Boo hoo. They will never match the new midpoint because the problem precondition declares that entries only occur twice, except for U. Definitely not O(n) if DELETE is not supported and for some stupid reason you can't just copy to a linked list, but "optimistic" for reasonable arraySize because U will be found sooner and not later. The execution time formula will be the arraySize raised to the second power, but divided by two. "The idea of the method of limits is simple and amounts to the following. In order to determine the exact value of a certain magnitude, we first determine not the magnitude itself but some approximation to it. However, we make not one approximation but a whole series of them, each more accurate than the last. Then from examination of this chain of approximation itself, we uniquely determine the exact value of the magnitude. By this method, *** which is in essence a profoundly dialectical one ***, we obtain a fixed constant as a result of a process or motion." - A. D. Aleksandrov, A. N. Kolmogorov and M. A. Lavrent'ev, MATHEMATICS: ITS CONTENT, METHODS AND MEANING (Matematika, ee soderzhanie metody i znachine). Original English edition: MIT Press, Cambridge MA. Dover 1999.
From: Arthur J. O'Dwyer on 10 Jun 2005 18:30 On Fri, 10 Jun 2005 spinoza1111(a)yahoo.com wrote: > > Darius wrote: >> ok here is a puzzle. >> there is an integer array whose length is odd, and all the numbers in >> the array appear exactly two times except one. Find the number in O(n) >> time. Try to do it without using any other data structure. > [...] > > Do while arraySize >= 2 > i = floor(arraySize/2) > j = i-1, k = i+1 > Do while j >= 0 or k < arraySize > if j>=0 and a[i]=a[j] { L = j, exit do } > if k<arraySize and a[i]=a[k] { L = k, exit do } > decrement j, increment k > End do > If j < 0 and k > arraySize return i > delete(i), delete(L) // Changes arraySize > End Do > > As long as DELETE is an atomic and fast operation this algorithm is > close to O(n) because the array gets smaller by two entries in the > worst case through its major loop, and in the worst case for the inner > loop (where the inner loop must search the entire array in both > directions) the algorithm is finished by definition. I think the above paragraph could be cleaned up to yield one of those clever "...and thus I am the Pope" arguments, but as it stands, it's too obviously confused to be convincing. Nilges' algorithm is O(n^2): we're doing O(n) linear searches of a linearly shrinking array. And yes, that's assuming DELETE is O(1), which it normally isn't. [snip much dissembling] The "trick" answer, which has already been posted, is definitely the one the OP['s instructor] was thinking of. It's actually quite elegant, IMHO, if not terribly useful for anything. -Arthur
From: pete on 10 Jun 2005 21:46
Arthur J. O'Dwyer wrote: > > On Fri, 10 Jun 2005 spinoza1111(a)yahoo.com wrote: > > > > Darius wrote: > >> ok here is a puzzle. > >> there is an integer array whose length is odd, > >> and all the numbers in > >> the array appear exactly two times except one. > >> Find the number in O(n) > >> time. Try to do it without using any other data structure. > > > [...] > > > > Do while arraySize >= 2 > > i = floor(arraySize/2) > > j = i-1, k = i+1 > > Do while j >= 0 or k < arraySize > > if j>=0 and a[i]=a[j] { L = j, exit do } > > if k<arraySize and a[i]=a[k] { L = k, exit do } > > decrement j, increment k > > End do > > If j < 0 and k > arraySize return i > > delete(i), delete(L) // Changes arraySize > > End Do > > > > As long as DELETE is an atomic and fast operation this algorithm is > > close to O(n) because the array gets smaller by two entries in the > > worst case through its major loop, > > and in the worst case for the inner > > loop (where the inner loop must search the entire array in both > > directions) the algorithm is finished by definition. > > I think the above paragraph could be cleaned up to yield one of > those clever "...and thus I am the Pope" arguments, but as it stands, > it's too obviously confused to be convincing. Nilges' algorithm is > O(n^2): It's *obviously* an order n squared algorithm. > And yes, that's assuming DELETE is O(1), which it normally isn't. -- pete |