For the example output, should it be 4 instead?
Input: A = [5,4,0,3,1,6,2]
Output: 6
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
For the example output, should it be 4 instead?
Input: A = [5,4,0,3,1,6,2]
Output: 6
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
In principle double precision has 52 sig-figs in binary expression, which is larger than int (31). That means pow(x, INT_MIN) could be any value as long as x is closer enough to +-1.
So perhaps the only workaround is to calculate pow(x, INT_MIN+1)/x, if the algorithm has utilized the Math.abs() function.
That could make some nasty corner cases.
Start from the second last step of the above solution, here is the somehow less dark-magical way to write the formula:
The goal is to emulate a ternary byte using two binary int. Then we need to implement the + operation between a ternary and a binary, without worrying about the carry digit.
First consider the + operation between a 4-nary and a binary. For each digit i in a binary, it is at most 1.
ab i ab
-----------
00 + 1 = 01
01 + 1 = 10
10 + 1 = 11
11 + 1 = 00 (mod 4)
So the digit newb is simply (b ^ i). Digit a has to add the carry digit from b, so new_a is ((b & i) ^ a).
Then we replace 11 by 00 since we want a ternary number. We xor both newa and newb by (newa & newb), which is 1 only when newa and newb are both 1.
Notice that each digit in the final result is either 0 or 1, which means only the lower digit b is non-zero and to be returned.
Here is the AC code. I guess it can be further simplified.
public int singleNumber(int[] nums) {
int a = 0;
int b = 0;
for (int i:nums){
int nb = (i^b)^(((i&b)^a)&(i^b));
int na = ((i&b)^a)^(((i&b)^a)&(i^b));
b = nb;
a = na;
}
return b;
}