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.

Why this is worth learning

Replace pair cancellation with per-bit counting modulo three. A triplicated value contributes either zero or three to every bit count, leaving only the singleton’s bit pattern.

Before coding: one-minute experiment

Why must the sign bit be included when the singleton is -2? What would reconstructing only bits 0..30 lose?

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
• -2^31 <= nums[i] <= 2^31 - 1, even on a 64-bit Go target.
• Exactly one value appears once; every other distinct value appears exactly three times.

Core idea (near-solution)

The XOR summary for pairs fails on triples because x XOR x XOR x=x. Retain a different summary: one occurrence count per bit, reduced modulo three. Each triplicated value contributes a multiple of three at every position, leaving exactly the singleton pattern. The position count is fixed at 32 by this problem’s value domain, and the sign position must be reconstructed too.

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

Invariant: during the scan, each count records the ones seen at that bit in the processed prefix. After all entries are processed, reducing each count modulo three removes complete triples and leaves the singleton bit.

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

For each of 32 bit positions, sum that position over the int32 representations of all inputs. Every repeated value contributes a multiple of three, so the remainder is exactly the singleton bit. Setting positions with nonzero remainder reconstructs its full 32-bit pattern. Building the result as int32 is necessary for a set sign bit to represent a negative value; converting that signed result back to int preserves the intended signed value. The existing int32 conversion makes this a 32-bit algorithm, not a full-width int algorithm on every architecture.

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.

Debugging lens

Test the signed-32-bit minimum, negative repeated values, and zero singleton. Do not silently broaden the domain beyond int32 while retaining a truncating implementation.

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.

Contract precision

The int signature carries signed-32-bit values for this exercise. Reconstruct all 32 bits into an int32, then convert that signed value to int. Values outside the stated range are unsupported; the reference’s narrowing conversion is not a full-width singleton algorithm.

Reconstruction checkpoint

Why must the sign bit be included when the singleton is -2? What would reconstructing only bits 0..30 lose?

Return to Bit Manipulation · Module quiz