Log inSign up
mediumLeetCodeNot Started

Single Number II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

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 O(n) and use only constant extra space O(1).

Example 1 · Example 1: Positive Integers:

Input: nums = [2, 2, 3, 2]
Output: 3
Explanation: 2 appears three times; 3 appears once.

Example 2 · Example 2: Negative and Large Integers:

Input: nums = [0, 1, 0, 1, 0, 1, 99]
Output: 99
Explanation: 0 and 1 appear three times; 99 appears once.

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each element in nums appears exactly three times except for one element which appears once.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Generalize single-number detection to arbitrary frequencies k using modulo arithmetic.
  • Design a finite state machine using bitwise boolean logic (&, ^, ~).
  • Process 32-bit signed integers and negative numbers safely without memory overhead.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Every element appears k times (k = 3) except one element.
  • Linear O(n) time and strict O(1) space constraints.
  • Modulo arithmetic on binary bit vectors.

Algorithmic Decision Tree:

  • Bit-column summation mod 3: loop 0 to 31, sum bits, set bit if sum % 3 != 0.
  • Or digital logic accumulator: ones = (ones ^ num) & ~twos; twos = (twos ^ num) & ~ones.

Connected Patterns:

Single NumberSingle Number IIIFind Two Non-Repeating Elements

1. Hash Map Frequency Counting

Intuition

Count frequencies in a hash map. Iterate entries to locate the key with count == 1.

When to apply: Basic baseline.

Algorithm

  1. Step 1: Build frequency map.
  2. Step 2: Loop entries: if value == 1, return key.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5using namespace std;
6
7int singleNumberBrute(const vector<int>& nums) {
8 unordered_map<int, int> freq;
9 for (int x : nums) freq[x]++;
10 for (auto& p : freq) {
11 if (p.second == 1) return p.first;
12 }
13 return -1;
14}
15
16int main() {
17 vector<int> nums = {2, 2, 3, 2};
18 cout << "Brute: " << singleNumberBrute(nums) << endl; // 3
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

2. Bit-by-Bit Column Sum Modulo 3

Intuition

Loop i from 0 to 31. Sum the i-th bit of all numbers. If sum % 3 != 0, set bit i in result. Handles signed 32-bit representation properly.

When to apply: When digital logic equations are unfamiliar; highly readable O(1) space method.

Algorithm

  1. Step 1: Set res = 0.
  2. Step 2: Loop i from 0 to 31: bitSum = 0.
  3. Step 3: For each x in nums: bitSum += (x >> i) & 1.
  4. Step 4: If bitSum % 3 != 0: res |= (1 << i).
  5. Step 5: Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int singleNumberColSum(const vector<int>& nums) {
7 int res = 0;
8 for (int i = 0; i < 32; ++i) {
9 int bitSum = 0;
10 for (int x : nums) {
11 bitSum += (x >> i) & 1;
12 }
13 if (bitSum % 3 != 0) {
14 res |= (1 << i);
15 }
16 }
17 return res;
18}
19
20int main() {
21 vector<int> nums = {2, 2, 3, 2};
22 cout << "Col Sum: " << singleNumberColSum(nums) << endl; // 3
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(32 * n)
  • Space complexity: O(1)

3. Digital Logic Bitmask Counter (ones, twos)

Intuition

Each bit position counts appearances modulo 3 using two state variables ones and twos. When a bit appears once, it is recorded in ones. When it appears twice, it moves from ones to twos. When it appears the third time, both ones and twos reset to 0. After all elements are processed, ones holds the bits of the unique single number.

When to apply: Optimal canonical solution: linear O(n) time, single pass, zero inner loops.

Algorithm

  1. Step 1: Set ones = 0, twos = 0.
  2. Step 2: For each num in nums:
  3. Step 3: ones = (ones ^ num) & ~twos.
  4. Step 4: twos = (twos ^ num) & ~ones.
  5. Step 5: Return ones.

Digital Logic Trace: nums = [2, 2, 3, 2]

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 1 (num = 2): ones = (0 ^ 2) & ~0 = 2
Visual state
Values and pointers at this exact step
pointers
S
ones=2, twos=0
0
↑ 1x
Check / comparison
ones = 2, twos = 0
Decision / next transition
First occurrence of 2.
Why this step matters

Step 1 (num = 2): ones = (0 ^ 2) & ~0 = 2. twos = (0 ^ 2) & ~2 = 0. State: 2 appeared 1 time.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int singleNumber(vector<int>& nums) {
9 int ones = 0, twos = 0;
10 for (int x : nums) {
11 ones = (ones ^ x) & ~twos;
12 twos = (twos ^ x) & ~ones;
13 }
14 return ones;
15 }
16};
17
18int main() {
19 Solution sol;
20 vector<int> nums1 = {2, 2, 3, 2};
21 cout << "Optimal: " << sol.singleNumber(nums1) << endl; // 3
22 vector<int> nums2 = {0, 1, 0, 1, 0, 1, 99};
23 cout << "Optimal: " << sol.singleNumber(nums2) << endl; // 99
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Map FrequencyO(n)O(n)Count occurrences of each number in a hash map; return key with count == 1.Hash map memory allocation.
2.Better — Bit-by-Bit Column Sum Modulo 3O(32 * n)O(1)For each of the 32 bit positions, sum bits across all numbers and compute sum % 3.32-bit column loop.
3.Optimal — Digital Logic Bitmask Counter (ones, twos)OptimalO(n)O(1)Simulate a 3-state counter (00 -> 01 -> 10 -> 00) for all 32 bits simultaneously using bitwise gates.Single linear iteration.

Common Pitfalls & Crucial Edge Cases

Signed integer overflow when reconstructing number from bits

In C++, 1 << 31 invokes undefined behavior on signed 32-bit ints. Use 1U << 31.

Attempting single XOR accumulator

XOR cancels pairs (modulo 2), not triplets (modulo 3).

Using O(n) extra space

Using a hash map violates the follow-up O(1) memory requirement.

Crucial Edge Cases to Validate:

  • Array of length 1 `[x]` — Returns x.
  • Unique number is negative — In languages like Java/C++, bit 31 is the sign bit; setting bit 31 naturally produces negative numbers in two's complement.
  • Unique number is 0 — Handled cleanly as 0 % 3 = 0.
  • Triplet elements are negative — Bit counts handle signed bits identically.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by explaining the general solution: count set bits at each position modulo k (here k = 3).
  2. Then demonstrate the optimal bitmask state machine using ones and twos to showcase advanced bit manipulation mastery.
  3. Discuss how this general technique applies when elements appear k times instead of 3.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.In Single Number II, every element appears 3 times except one. What is the bitwise modulo 3 strategy?

2.What digital logic state machine achieves this bit-counting in O(1) space?

3.What is the time complexity of the bit-by-bit modulo 3 approach?

Back to DSA Sheet