3 ms·
Unfortunately no, 0 also can't be handled. The chains are 1 -> 2 -> -1 -> -2 -> 1 3 -> 4 -> -3 -> -4 -> 3 .... 2^31 - 3 -> 2^31 - 2 -> -2^31 + 3 -> -2^31 +
by anonymous 13y ago
Unfortunately no, 0 also can't be handled.
The chains are
1 -> 2 -> -1 -> -2 -> 1
3 -> 4 -> -3 -> -4 -> 3
....
2^31 - 3 -> 2^31 - 2 -> -2^31 + 3 -> -2^31 + 2 -> 2^31 - 3
And now you're left with just 2^31 - 1, -2^31, -2^31 + 1, 0. If you define f(f(0)) = 0, then you have only 3 numbers and you need 4 for a chain.
Possible solutions:
* f(f(0)) = -2^31
* crash on any of the 3
* crash violently
* enter an endless loop (technically if the function never completes, it doesn't return a wrong value)
- colanderman 13y agoAnd now you're left with just 2^31 - 1, -2^31, -2^31 + 1, 0. If you define f(f(0)) = 0, then you have only 3 numbers and you need 4 for a chain. The parent of your post explicitly said: all but one number (2^n - 1) correct.
- danbruc 13y agoHere the example for 3 bits. 0 -> 0 +1 -> -2 -> -1 -> +2 -> +1 +3 -> -4 -> -3 -> -4 The first cycle takes care of 0, the second one of -2, -1, +1 and +2. The interesting thing is the third thing - it consists of the cycle -4 -> -3 -> -4 and the attached chain +3 -> -4 entering the cycle via -4. This one correctly maps +3 to -3 and -4 to -4 (-(2^(n - 1) is its on inverse) and only fails for -3 which is incorrectly mapped to itself, too. There you go, 7 out of 8 correct. (This is the essence of my way longer answer on Stack Overflow [1] although it is not necessarily any clearer because it evolved a lot.) [1] http://stackoverflow.com/a/731857 http://stackoverflow.com/a/731857