137

137. Single Number II (Medium)

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Each element in nums appears exactly three times except for one element which appears once.

Related Topics:
Array, Bit Manipulation

Similar Questions:

• Single Number (Easy)
• Single Number III (Easy)

Note

Basically this problem asks us to implement a ternary system that when a digit reaches 3, this digit should be reset to 0.

Solution 1. Bit Manipulation

For each bit for each number, if the bit is 1 for 3 times, reset it to 0. The leftover is the bit for the single number.

// OJ: https://leetcode.com/problems/single-number-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unsigned ans = 0;
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            for (unsigned n : nums) {
                cnt = (cnt + ((n >> i) & 1)) % 3;
            }
            ans |= cnt << i;
        }
        return ans;
    }
};

Solution 2. Bit Manipulation

Instead of counting each bit separately, we compute all the bits together.

Since we are simulating a ternary system, we need two binary bits to represent each ternary digit.

$(00)_2 = (0)_3$

$(01)_2 = (1)_3$

$(10)_2 = (2)_3$

$(11)_2 = (0)_3$ When the ternary digit becomes 3, we reset it to 0 instead of carrying it over to the higher digit

We use high/low to represent all the left-/right-most bits of each ternary digit.

high and low won't have 1 at the same bit index, because it means that the ternary digit is 3 and should be reset to 0.

For each number n in nums array:

1. For the bit 1s that n and low DO NOT share in common (i.e. n ^ low), they are left as the new low. So, newLow = low ^ n
2. For the bit 1s that n and low share in common (i.e. n & low), they become new high digits. Together with the old high digits, newHigh = high | (n & low).
3. If newLow and newHigh share any digit 1s in common, they should be reset to 0. So we should remove newLow & newHigh from newLow and newHigh

// OJ: https://leetcode.com/problems/single-number-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int low = 0, high = 0;
        for (int n : nums) {
            int newLow, newHigh;
            newLow = low ^ n;
            newHigh = high | (low & n);
            low = newLow ^ (newLow & newHigh);
            high = newHigh ^ (newLow & newHigh);
        }
        return low;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/single-number-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int low = 0, high = 0;
        for (int n : nums) {
            high ^= low & n;
            low ^= n;
            unsigned mask = ~(high & low);
            high &= mask;
            low &= mask;
        }
        return low;
    }
};

Solution 4.

a ^ b has 1 in the bits where the corresponding bits in a and b are different, and 0 in the others. 0011 ^ 0101 = 0110

a & ~b has the same bits as in a expect that those bits that are 1 in b are cleared as 0. 0011 & ~0101 = 0010

To get the new one: *

                 n:  0 0 0 0 1 1 1 1
               one:  0 0 1 1 0 0 1 1
               two:  0 1 0 1 0 1 0 1

             one^n:  0 0 1 1 1 1 0 0 // The bits that are `1`s after adding `one` and `n`.
one = (one^n)&~two:  0 0 1 0 1 0 0 0 // The bits summing to `3` are cleared from `one^n`. They are the ones that are `1`s both in `one^n` and `two`.
             two^n:  0 1 0 1 1 0 1 0 // The bits that are `1`s after adding `two` and `n`.
      (two^n)&~one:  0 1 0 1 0 0 1 0 // The bits summing to `3` are cleared from `two^n`. They are the ones that are `1`s both in `two^n` and `one`.

// OJ: https://leetcode.com/problems/single-number-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/single-number-ii/discuss/43294/Challenge-me-thx
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for (int n : nums) {
            one = (one ^ n) & ~two;
            two = (two ^ n) & ~one;
        }
        return one;
    }
};