How do you approach Single Number II?

A hash map of counts works in O(n) time but O(n) space. Start there if you're stuck, then look for something slicker.

What is the time complexity of Single Number II?

Time complexity: O(n). Space complexity: O(n) for the set of distinct values.

What are common mistakes on Single Number II?

Shifting by at least the word width, which is undefined or wraps depending on the language. Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends. Precedence: & and | bind more loosely than the comparison operators, so a & 1 == 0 does not mean what it looks like.

gitGood.dev

← Back to problems

Single Number II

MediumAlgorithms

Description

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.

You must implement a solution with linear runtime complexity.

Example 1

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

Output: 3

Example 2

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

Output: 99

Example 3

Input: nums = [-2,-2,1,-2]

Output: 1

Constraints

- 1 <= nums.length <= 3 * 10^4 - -2^31 <= nums[i] <= 2^31 - 1 - Each element in nums appears exactly three times except for one element which appears once.

Single Number II: approach, complexity and pitfalls

A medium bit manipulation problem, graded against 7 test cases (4 of them hidden).

The pattern: Bit Manipulation

XOR, masks, and shifts - constant-space tricks for counting and pairing.

Reach for it when you see: "Appears once/twice", powers of two, or an explicit O(1) space requirement.

If you are stuck

Show the 3-step hint ladder

A hash map of counts works in O(n) time but O(n) space. Start there if you're stuck, then look for something slicker.
Consider sum(set(nums)): every distinct value counted once. How does 3 times that compare to the plain sum of nums?
3 * sum(set) counts every element three times, but the single one was only present once - so 3 * sum(set) - sum(nums) equals exactly twice the single number.

The optimal approach

Show the approach: Set-Sum Arithmetic

Let `S` be the sum of distinct values and `T` the total sum. Tripling `S` counts every value three times, but the singleton actually contributed only once to `T` - the difference `3S - T` therefore equals exactly `2x` where `x` is the answer, so `x = (3S - T) / 2`. The division is always exact, so integer division is safe in both languages.

A classic alternative uses per-bit counters mod 3 for O(1) extra space, but it needs careful 32-bit sign handling (especially in Python); the set-sum approach is the cleanest correct O(n) solution.

Time: O(n)
Space: O(n) for the set of distinct values

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Bit Manipulation mistakes

These apply to the pattern as a whole, not just this problem.

Shifting by at least the word width, which is undefined or wraps depending on the language.
Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends.
Precedence: `&` and `|` bind more loosely than the comparison operators, so `a & 1 == 0` does not mean what it looks like.