3 ms·
Here's a counterexample. Sequence is [1, 2, 3, 4, 6, 6, 7, 8, 9, 10] so m = 5 and d = 6 diff = 5-6 = -1 xor = 5^6 = 3 1-2 = -1 1^2 = 3 5-6 = -1
by pedrocr 16y ago
Here's a counterexample.
Sequence is [1, 2, 3, 4, 6, 6, 7, 8, 9, 10] so m = 5 and d = 6
diff = 5-6 = -1
xor = 5^6 = 3
1-2 = -1
1^2 = 3
5-6 = -1
5^6 = 3
9-10 = -1
9^10 = 3
So three different combinations, within N, that obey the two constraints
- biobot 16y agoMake sense! That fails my solution!
- biobot 16y agoOK. I think I find a way around. Assume d XOR m = a. Find k = position of the first bit (from MSB to LSB) in a. Then d + m can be in [a + 2^(k+1),a + 2^(k+2),...,a + 2^63]. We will have less than 63 cases. In each case, after we find d and m, make sure they are in range and then linear test. So in the end, we may need to run at most 63+3 = 66 N. But it still linear though.