Code Implementation

class Solution:
    def singleNumber(self, nums):
        ones, twos = 0, 0
        for num in nums:
            ones = (ones ^ num) & ~twos
            twos = (twos ^ num) & ~ones
        return ones
      

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
};
      

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}
      

var singleNumber = function(nums) {
    let ones = 0, twos = 0;
    for (let num of nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;
};
      

Problem Description

Given a non-empty array of integers nums, every element appears exactly three times except for one element, which appears exactly once. Find and return the single element that appears only once.

• You must solve the problem in linear runtime complexity and constant extra space.
• Assume there is exactly one solution and you may not modify the input array.

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

Thought Process

At first glance, you might think to use a hash map or dictionary to count the occurrences of each number, then return the one that appears only once. This is straightforward, but it uses extra space proportional to the number of unique elements.

However, the problem requires constant extra space. We need to rethink our approach. Since every number except one appears exactly three times, maybe we can use bitwise operations to track how many times each bit appears across all numbers.

The key insight is: if we sum up each bit position across all numbers, the bits belonging to numbers that appear three times will contribute multiples of three. The bits of the unique number will not. By isolating these, we can reconstruct the single number without extra space.

Solution Approach

To solve this problem efficiently, we use bit manipulation. Here’s how:

1. We maintain two variables, ones and twos, to record the bits that have appeared once and twice, respectively.
2. As we process each number in the array:
   • ones holds the bits which have appeared once so far (but not twice or three times).
   • twos holds the bits which have appeared twice so far (but not three times).
3. For each number, update ones and twos as follows:
   • ones = (ones ^ num) & ~twos: Add bits from num to ones if they haven't appeared in twos.
   • twos = (twos ^ num) & ~ones: Add bits from num to twos if they haven't appeared in ones.
4. This way, once a bit has appeared three times, it is cleared from both ones and twos.
5. At the end, ones contains the unique number that appeared only once.

This method is efficient because it only uses a constant amount of extra space and processes the array in a single pass.

Example Walkthrough

Let's walk through the example nums = [2, 2, 3, 2]:

• Start: ones = 0, twos = 0
• First 2:
  • ones = (0 ^ 2) & ~0 = 2
  • twos = (0 ^ 2) & ~2 = 0
• Second 2:
  • ones = (2 ^ 2) & ~0 = 0
  • twos = (0 ^ 2) & ~0 = 2
• 3:
  • ones = (0 ^ 3) & ~2 = 1
  • twos = (2 ^ 3) & ~1 = 2
• Third 2:
  • ones = (1 ^ 2) & ~2 = 0
  • twos = (2 ^ 2) & ~0 = 0

After processing all numbers, ones = 3. This is the single number that appears only once.

Time and Space Complexity

Brute-force approach:

• Time complexity: O(n), since we would count occurrences for each number using a hash map.
• Space complexity: O(n), due to the storage of counts for each unique number.

• Time complexity: O(n), because we process each element exactly once.
• Space complexity: O(1), since we only use a fixed number of integer variables regardless of input size.

Summary

This problem challenges us to find a unique element in an array where every other element appears three times, using only constant extra space. By leveraging bitwise operations and clever state tracking with two variables, we efficiently isolate the unique number. This method is both space- and time-optimal, demonstrating the power of bit manipulation for specialized counting problems.