Skip to main content

137. Single Number II

medium

Every element appears three times except one. Find the singleton in linear time and constant space. Forces you to generalize the XOR trick to mod-3 bit counting.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 a linear runtime complexity and use only constant extra space.

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.

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

XOR alone doesn't work because three copies of x XOR'd together is x, not 0.

Hint 2

Think bit-by-bit. For each of the 32 bit positions, sum the bit across all numbers — that sum mod 3 is the singleton's bit at that position.

Hint 3

There's a cleverer O(1)-state trick using two integers ones and twos that act as a mod-3 counter at each bit position.

Solution approach

Reveal approach

Two clean approaches. Bit-counting: for each of 32 bit positions, sum that bit across all numbers; result bit i is sum_i mod 3. O(32n) time, O(1) space. Two-counter trick: maintain two integers ones and twos. For each num, update ones = (ones ^ num) & ~twos, then twos = (twos ^ num) & ~ones. At any moment ones holds bits that have been seen 1 mod 3 times and twos holds bits seen 2 mod 3 times. After the loop, ones is the singleton. Both are O(n) time, O(1) space; the bit-count version is easier to derive on the spot.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Single Number II and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →