 BiruLyu
5/25/2017 - 9:17 PM

## 137. Single Number II(extend to m times and p times).java

``````public class Solution {
public int singleNumber(int[] nums) {
int one = 0;
int two = 0;
int mask = 0;
for(int num : nums){
two ^= num & one;
//two |= num & one;
one ^= num;
mask = ~ (one & two);
}

return one;
}
}

/*

00 => 01 => 10 => 00

[7, 7, 7, 3]

one  0 0 0
two  0 0 0

first 7:
one  1 1 1
two  0 0 0

second 7:

one  0 0 0
two  1 1 1

third 7:

one  0 0 0
two  0 0 0

first 3:

one  0 1 1
two  0 0 0

return 3

extend to five times

000 => 001 => 010 => 011 => 100 => 000
[7, 7, 7, 7, 7, 3]

three ^= num & one & two;
two ^= num & one;
one ^= num;

mask = ~ (one & ~two & three); //when == 101, go back to 000

*/``````
``````/*
There are many numbers appearing m times, and only one number appearing p times. Find the number that appears p times.

https://discuss.leetcode.com/topic/11877/detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers

xm, xm-1, xm-2, ... x1;

xm = xm ^ (xm-1 & xm-2 & ... & x1 & num)
x1 = x1 ^ num
mask = ~ (x1 & ) // according to k

*/

class Solution {
public int singleNumber(int[] nums) {
int x1 = 0, x2 = 0, x3 = 0, mask = 0;

for (int n : nums) {
x3 = x3 ^ (x2 & x1 & n);
x2 = x2 ^ (x1 & n);
x1 = x1 ^ n;
mask = ~ (~x1 & ~x2 & x3);
x1 = x1 & mask;
x2 = x2 & mask;
x3 = x3 & mask;
}
return x2;

}
}``````