Single Number II

Bit ManipulationArray

20 min

Problem Statement

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.

Examples

Example 1:

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

Output: 3

Example 2:

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

Output: 99

Solution (Bit Counting)

Since XORing doesn't work when numbers appear three times, we need a different approach. We can count the number of times each bit (from 0 to 31) is set to 1 across all numbers in the array.

For each bit position, the total count of set bits will be a multiple of 3 if the single number does not have that bit set. If the single number *does* have that bit set, the count will be 3k + 1.

Algorithm Steps

Initialize the result to 0.
Iterate through each bit position from 0 to 31.
For each bit position, calculate the sum of that bit for all numbers in the array.
If the sum for a bit position is not a multiple of 3 (i.e., sum % 3 != 0), it means the single number has this bit set.
Set the corresponding bit in the result.
After checking all bits, result will be the single number.

Array `nums`:

Checking Bit: -1

Bit Sum: 0

Result: 0000 (0)

Initialize result = 0

Single Number II Solution


class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ans = 0
        for i in range(32):
            sum = 0
            for num in nums:
                if ((num >> i) & 1) == 1:
                    sum += 1
            if sum % 3 != 0:
                ans |= (1 << i)
        
        # Handle negative numbers
        if ans >= 2**31:
            ans -= 2**32
            
        return ans