Is Single Number II easy or hard?

Single Number II is rated Medium on LeetCode. The hash map solution is straightforward, but the expected optimal answer requires understanding bit manipulation and modular arithmetic.

Single Number II Python/Java solution

In Python or Java, the typical implementation loops through 32 bit positions, counts set bits across the array, and reconstructs the answer using bit operations. The algorithm runs in O(n) time and uses constant space.

How to solve Single Number II in O(n)?

Iterate over each bit position and count how many numbers in the array have that bit set. Since all repeating numbers appear three times, their contributions cancel when you compute count % 3. Reconstruct the single number from the remaining bits.

What is the best approach for Single Number II?

The optimal approach uses bit manipulation with modulo arithmetic. Count how many numbers have each bit set from 0 to 31, then take the count modulo 3. Bits that remain correspond to the unique number. This runs in O(n) time and O(1) extra space.

Is Single Number II asked at Google/Amazon/Meta?

Single Number II is a common bit manipulation interview problem and variations have appeared at companies like Amazon, Google, and Meta. It tests understanding of binary operations, modular arithmetic, and space optimization.

What data structure is used in Single Number II?

Two common approaches exist. A hash map can store frequencies of each number, while the optimal solution avoids extra data structures by using bit manipulation and integer variables.

What is the time complexity of Single Number II?

The optimal bit manipulation solution runs in O(n) time because the array is scanned while counting bits. Since there are only 32 bit positions for integers, the constant factor remains small. Space complexity is O(1).

Description Solution Video 31:19

137. Single Number II

Medium68.0% acceptance5 companies

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.

Example 1:

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

Example 2:

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

Constraints:

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