Another simple but easy to understand C++ solution, 12ms


  • 0
    X

    The simplest solution in C++ is
    https://leetcode.com/discuss/43377/the-simplest-solution-ever-with-clear-explanation
    but it has some dark magic.

    This solution is also simple

    int singleNumber(vector<int>& nums) {
        int low = 0, high = 0;
        for (auto x : nums) {
            int low_t = x & ~low & ~high;
            int high_t = x & low & ~high;
            low = low_t | (low & ~x);
            high = high_t | (high & ~x);
        }
        return low;
    }
    

    This code also mimics ternary operation, but just look at the truth table.

    When x = 1, low = 0, high=0, then low = 1.
    When x = 1, low = 1, high=0, then high = 1.
    Otherwise both should be 0, but we should not discard current results if the last result is 1, x = 0, for both low and high, because we are counting.

    Thanks.


Log in to reply
 

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