Description Link to heading

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 * 10⁴
  • -2³¹ <= nums[i] <= 2³¹ - 1
  • Each element in nums appears exactly three times except for one element which appears once.

Solution Link to heading

To ensure a space complexity of $O(1)$, we must contemplate the binary representation of nums, specifically tallying the sum of each digit in nums[i]. Given that only one element appears once, while others manifest thrice, we can apply a modulo operation of this sum by 3. The resulting outcome represents the digits of the sought-after element.

Code Link to heading 

class Solution {
  public:
    int singleNumber(vector<int> &nums) {
        vector<int> cnt(32);
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 32; ++j) {
                cnt[j] += ((nums[i] >> j) & 0x1);
            }
        }
        for (int i = 0; i < 32; ++i) {
        	cnt[i] = cnt[i] % 3;
        }
        int res = 0;
        for (int i = 0; i < 32; ++i) {
        	res |= (cnt[i] << i);	
        }
        return res;
    }
};