Single Number II

MediumBit Manipulationbit counting

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an integer array nums in which **every element appears exactly three times**, except for a single element that appears **exactly once**. Return the element that appears only once. You must design an algorithm that runs in **linear time** O(n) and uses only **constant extra space** O(1) (so you cannot, for example, build a hash map that grows with the input). The intended approach exploits how bits behave under counting: if you tally the number of set bits across all elements at each bit position, every bit contributed by the triplicated values forms a count that is a multiple of three. Whatever remains after taking each bit count modulo 3 reconstructs the lonely element.

Examples

Input: nums = [2, 2, 3, 2]
Output: 3
The value `2` appears three times, while `3` appears once, so `3` is the answer.
Input: nums = [0, 1, 0, 1, 0, 1, 99]
Output: 99
Both `0` and `1` appear three times each; only `99` is unique.
Input: nums = [-4, -4, -4, 7]
Output: 7
Negative duplicates also cancel out under bit counting, leaving `7`.

Constraints

  • `1 <= nums.length <= 3 * 10^4`
  • `-2^31 <= nums[i] <= 2^31 - 1`
  • Every element of `nums` appears exactly three times except for one element which appears exactly once.
  • Your solution must run in `O(n)` time and use `O(1)` extra space.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.