Single Number II — Solution

Problem

Every number in the array appears exactly three times — except for one number that appears exactly once. Find and return that unique number. The problem specifically asks for a solution that runs in linear time and uses constant extra space.

• Input: nums = [2, 2, 3, 2]
• Output: 3
• Explanation: 2 appears three times; 3 is the unique element.

Second example:

• Input: nums = [0, 1, 0, 1, 0, 1, 99]
• Output: 99
• Explanation: 0 and 1 each appear three times; 99 appears once.

Intuition

The obvious approach — XOR all elements — fails here because XOR cancels pairs (a ^ a = 0), but three copies of a number (a ^ a ^ a = a) don't cancel. The constant-space insight is to think at the bit level: if you count how many numbers in the array have a 1 at each bit position, every tripled number contributes a multiple of 3 to that count. Taking the count at each bit position mod 3 zeroes out all tripled numbers' contributions, leaving only the unique number's bits.

Approach 1 — Hash Map Counter

Count how many times each number appears, then return the one with a count of 1. Straightforward and handles any "every element appears k times except one" variant without modification.

1. Iterate through the array and build a frequency map.
2. Iterate through the map entries.
3. Return the key whose value equals 1.

1from collections import Counter
2
3class Solution:
4    def singleNumber(self, nums: list[int]) -> int:
5        frequency = Counter(nums)
6        for num, count in frequency.items():
7            if count == 1:
8                return num

Time: O(n) — two linear passes over n elements.
Space: O(n) — the frequency map stores at most n/3 + 1 distinct keys.

Approach 2 — Bit Counting

For each of the 32 bit positions, sum how many input numbers have a 1-bit there, then take that sum mod 3. Bits from numbers that appear three times contribute a sum divisible by 3, which vanishes under mod. The remaining 1-bits belong to the unique number.

1. Initialize result = 0.
2. For each bit position 0 through 31: a. Count how many numbers in nums have a 1-bit at that position. b. If count % 3 != 0, set that bit in result.
3. In Python only: if result represents a negative 32-bit integer (bit 31 is set), convert it from unsigned to signed by subtracting 2³².
4. Return result.

1class Solution:
2    def singleNumber(self, nums: list[int]) -> int:
3        result = 0
4        for bit_position in range(32):
5            bit_sum = sum((num >> bit_position) & 1 for num in nums)
6            # Tripled numbers contribute a multiple of 3 to bit_sum; mod isolates the unique number's bit
7            if bit_sum % 3 != 0:
8                result |= (1 << bit_position)
9        # Python integers are arbitrary-precision, so manually apply 32-bit signed interpretation
10        if result >= (1 << 31):
11            result -= (1 << 32)
12        return result

Time: O(32n) = O(n) — 32 passes, each touching all n elements.
Space: O(1) — only a fixed number of integer variables regardless of input size.

Complexity Summary

Common Mistakes

• Applying XOR like Single Number I — XOR cancels pairs (a ^ a = 0) but three copies leave a residue (a ^ a ^ a = a), so naively XOR-ing everything doesn't isolate the unique element.
• Using mod 2 instead of mod 3 — bit_sum % 2 is the right operation for pairs; for triplets you must use bit_sum % 3.
• Skipping the signed-integer conversion in Python — Python integers are unbounded, so a "negative" answer like -2 reconstructs as 4294967294. The check if result >= (1 << 31): result -= (1 << 32) is required.
• Not shifting the bit sum before ORing — Writing result |= (bit_sum % 3) (missing << bit_position) always modifies only bit 0 instead of the correct bit position.
• Mixing up state when using the ones/twos state-machine variant — If you compute the new value of ones first and then use it to update twos, you corrupt the state; both must be updated using the old values of each other simultaneously.

Related Problems

• single-number — The simpler version where every element appears twice except one; pure XOR solves it in one pass.
• missing-number — Find the absent value in a 0–n range; the same "isolate the odd one out" flavor, solvable with XOR or arithmetic.
• counting-bits — Count 1-bits in every integer from 0 to n; builds the same intuition for reasoning about bit positions across a set of numbers.
• number-of-1-bits — Count 1-bits in a single integer; foundational practice for the bit-extraction step used in Approach 2.
• reverse-bits — Reverse the 32 bits of an integer; exercises the same bit-position-by-bit-position construction pattern.