puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Emlyn Corrin on 21 Jun 2005 04:04 Mike wrote: > So as an alternative solution, how > about: > > function ReturnOddElement(A : array of integer) : integer; > var > p : integer; > i : integer; > begin > p := 1; > for i := Low(A) to High(A) do > if (p mod A[i]) = 0 > then > p := p div A[i] > else > p := p * A[i]; > result := p; > end; > > This requires no bitwise operations and will be O(n) on any > system on which MaxInt is sufficiently large. > > Mike. > Very clever, but unfortunately it doesn't work, try it on the sequence 6, 2, 3, 4, 2, 3, 6 Emlyn
From: spinoza1111 on 21 Jun 2005 04:12 Chris Dams wrote: > On Mon, 2005-06-20 at 00:13 -0700, spinoza1111(a)yahoo.com wrote: > > > Of course, this remains a stunning irrevelance to the fact that the XOR > > algorithm cannot be said to be O(n), because it replaces equality in an > > operation that is from the standpoint of big O theory not valid. You > > have to assume that "in addition to test for equality, we can regard > > numbers as bitwise accessible". > > Of course not. Even if the bitwise representation is not accessible any > language that allows division by two can easily be used to make you own > binary representation. The algorithm will still be O(n). Yes, but...its execution time will be n*W, a constant (the bit width) which is rather large. The XOR solution continues to suck. Once you drop the assumption of an atomic XOR, you have a BAD O(n) algorithm. One that continues not to work for floating point arrays.
From: Emlyn Corrin on 21 Jun 2005 06:55 spinoza1111(a)yahoo.com wrote: > > Mike wrote: >>function ReturnOddElement(A : array of integer) : integer; >>var >> p : integer; >> i : integer; >>begin >> p := 1; >> for i := Low(A) to High(A) do >> if (p mod A[i]) = 0 >> then >> p := p div A[i] >> else >> p := p * A[i]; >> result := p; >>end; >> >>This requires no bitwise operations and will be O(n) on any >>system on which MaxInt is sufficiently large. > > > STILL fails to work for floating point systems because in FP systems > there can be >1 bitwise representation of the same n. > Did you actually try to understand the code? The reason it doesn't work has nothing at all to do with the possible bitwise representations. Emlyn
From: pete on 21 Jun 2005 09:23 spinoza1111(a)yahoo.com wrote: > The XOR solution continues to suck. Once you drop the assumption of an > atomic XOR, you have a BAD O(n) algorithm. The one and only BAD thing about it, is that you didn't think of it first. Even if the XORing were to be accomplished by a complicated function, it would still fit the specification perfectly. Do you think that the point of having specifications is so that you can do whatever you want and the customer still has to pay? > One that continues not to > work for floating point arrays. Note that floating point still has nothing to do with the puzzle. An simple O(n*log(n)) solution for floating types would be to heapsort the array and do a sequential check for equality. So, your Stupid solution is the still the worst. The clever part of your Stupid solution is especially stupid. You have no reason to assume that the unique value is in the middle half of the array. Therefore on average, your search pattern just slows everything down. -- pete
From: pete on 21 Jun 2005 09:33
pete wrote: > > spinoza1111(a)yahoo.com wrote: > > > The XOR solution continues to suck. > > Once you drop the assumption of an > > atomic XOR, you have a BAD O(n) algorithm. > > The one and only BAD thing about it, > is that you didn't think of it first. > Even if the XORing were to be accomplished > by a complicated function, > it would still fit the specification perfectly. > > Do you think that the point of having specifications > is so that you can do whatever you want > and the customer still has to pay? /* BEGIN puzzle.c */ #include <stdio.h> #include <limits.h> void xor_int(int *answer, int *array); unsigned char byte_xor(unsigned char answer, unsigned char array); int main(void) { size_t index; int answer; int array[] = {-0,-7,-1,2,-3,4,5,-6,-6,5,4,-3,2,-1,-0}; answer = 0; for (index = 0; index != sizeof array / sizeof *array; ++index) { if (array[index] != 0) { xor_int(&answer, array + index); } } printf("The unique value is %d.\n", answer); return 0; } void xor_int(int *answer, int *array) { unsigned char *ans = (unsigned char *)answer; unsigned char *arr = (unsigned char *)array; size_t n = sizeof *answer; while (n-- != 0) { *ans++ = byte_xor(*ans, *arr++); } } unsigned char byte_xor(unsigned char answer, unsigned char array) { unsigned char result = 0; unsigned mask = 1; size_t bit = CHAR_BIT; while (bit-- != 0) { if ((answer + array) % 2 == 1) { result += mask; } mask *= 2; answer /= 2; array /= 2; } return result; } /* END puzzle.c */ -- pete |