Self-explanatory solution in C++ using little extra but constant memory


  • 2
    H

    I regrettably had to give up and resort to the previous solutions for this one. Here is my attempt at making the code itself understandable and reflect the idea behind the solution. Extra memory is used to make the code clearer. If the problem is generalized to:
    Find the single element where the other elements are repeated K times,
    then the space complexity is O(K).

    Here I try to elaborate MissMary's explanation with my own words, which generally is to loop the bits with a period of 3. Imagine an array, seen[3], as a 2D bit field like this:

    seen[2]: 1 1 1 1 1
    seen[1]: 0 0 0 0 0
    seen[0]: 0 0 0 0 0
    

    Then the k-th bit in seen[i] means that this k-th bit has been seen for i+1 times so far in the processed numbers. Now suppose we are processing the next number, x = 00101, in binary representation. So we should move the first and third least-significant bits from seen[2] to seen[0].

    Before the move:

    seen[2]: 1 1 1 1 1     /\
    seen[1]: 0 0 0 0 0    /||\  move bits this way, and wrap around from seen[2] to seen[0]
    seen[0]: 0 0 0 0 0     ||
    ------------------
       x   : 0 0 1 0 1  
    

    where the set bits (i.e., bits that are 1) in x indicate the columns to move up bits in the bit field.

    After the move:

    seen[2]: 1 1 0 1 0     /\
    seen[1]: 0 0 0 0 0    /||\  move bits this way, and wrap around from seen[2] to seen[0]
    seen[0]: 0 0 1 0 1     ||
    ------------------
       x   : 0 0 1 0 1  
    

    After processing a same number for three times in this way, the bits in the bit field would all return to seen[2]. When all numbers in the input array are processed this way, all bits in the bit field would return to seen[2], except for the set bits in the single number, since those bits are moved one extra time, by the unknown single number, and to the seen[0] row of the bit field. Thus, the seen[0] row in the bit field is the single number that we look for.

    And here is the code:

    class Solution {
    public:
        int singleNumber(int A[], int n) {
            int seenOnce = 0;
            int seenTwice = 0;
            int seenThrice = ~0x0;
            int move1to2, move2to3, move3to1; // bits to be moved
            int x;
            for (int i = 0; i < n; ++i) {
                x = A[i];
                move1to2 = seenOnce & x;
                move2to3 = seenTwice & x;
                move3to1 = seenThrice & x;
                // use bit-wise XOR to flip the bits, in order to move in/out the bits
                //
                //            +-- move in
                //            |
                //            |          +-- move out
                //            |          |
                //            v          v
                seenOnce   ^= move3to1 | move1to2;
                seenTwice  ^= move1to2 | move2to3;
                seenThrice ^= move2to3 | move3to1;
            }
            return seenOnce;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.