Given n numbers where every number appears three times except one which appears only once, find that single number (in linear time and space).
I’m sure everyone knows the two-number version — just use XOR.
Initially I used a map to solve it, but that didn’t feel like it met the problem’s intent. After reading others’ approaches, I realized it’s a variation of the same idea. I feel like I need to improve at generalizing solutions and analyzing problems.
The purpose of XOR is to count the number of 1s at each bit position, and reset to zero when the count reaches two.
Similarly, for three numbers, we reset to zero when the count reaches three.
Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int singleNumber(int A[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int now = A[0];
        int one = now;
        int two = 0;
        int three = 0;
        for(int i = 1; i < n; i++)
        {
            int input = A[i];
            int in1 = one & input;
            one = one ^ input;
            int in2 = two & in1;
            two = two ^ in1;

            one = one ^ in2;
        }
        return one ^ two;
    }
};