Problem #137: Single Number II

Intuition & Strategy Breakdown

Count bits at each of the 32 position bits across all numbers. Bit count modulo 3 gives the bits belonging to the single element.

Python Solution

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            count = 0
            for num in nums:
                if (num >> i) & 1:
                    count += 1
            if count % 3:
                # If we're at the 31st bit (sign bit), 
                # handles negative numbers properly
                if i == 31:
                    ans -= (1 << i)
                else:
                    ans |= (1 << i)
        return ans

Java Solution

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                if (((num >> i) & 1) != 0) {
                    count++;
                }
            }
            if (count % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}