Single Number II

Given an array where every element appears three times except one, return the single one. A frequency map is simple but can be avoided.

Function signature

func SingleNumberII(nums []int) int

Inputs / outputs

• nums: array of integers.
• Return: the element that appears once.

Example

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

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

Count bits at each position. Triplicate contributions sum to multiples of 3, so count % 3 reveals the unique number's bit.

Invariant: for each bit position, the count modulo 3 equals the bit of the single number.

Algorithm (step-by-step)

1. For each bit 0..31, count how many numbers have that bit set.
2. If count % 3 == 1, set that bit in the result.
3. Return the reconstructed integer.

Correctness sketch

• Invariant: for each bit position, the count modulo 3 equals the bit of the single number.
• Bitwise operations preserve the required per-bit invariant.
• Combining results across bits reconstructs the correct value.
• Therefore the final bit-accumulated result is correct.

Trace (hand walkthrough)

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

Walk:
- bit0 count = 1 (from 3) -> 1 mod3
- bit1 count = 4 (2,2,2,3) -> 1 mod3
- reconstruct bits -> 3

Pitfalls to avoid

• Forgetting to handle the sign bit (use 32-bit arithmetic).
• Using 64-bit shifts on 32-bit assumptions.

Complexity

• Time: O(32*n).
• Extra space: O(1).

Implementation notes (Go)

• Convert each value to int32 during bit checks to match 32-bit behavior.