How do you solve Single Number II on LeetCode?

Single Number II (LeetCode #137) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using bit manipulation can significantly reduce time complexity.

What is the time complexity of Single Number II?

The optimal solution for Single Number II runs in O(n) time and uses O(1) space. This complexity is linear because we only pass through the array once, and we use constant space for the variables.

What is the brute force solution for Single Number II?

The brute force approach for Single Number II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks each element and counts its occurrences in the array. If an element appears once, we return it. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Single Number II?

Single Number II uses the following concepts: Array, Bit Manipulation. The recommended patterns to study are: Bit Manipulation, Array.

What are the interview tips for Single Number II?

Explain your thought process clearly before coding. Be prepared to discuss trade-offs of different approaches. Practice bit manipulation problems to become comfortable with them.

What are common mistakes when solving Single Number II?

Not understanding how bitwise operations work. Confusing the roles of ones and twos in the optimal solution.

#137

Single Number II

Medium

ArrayBit ManipulationBit ManipulationArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses bit manipulation to find the unique number. By leveraging the properties of binary representation, we can efficiently count bits and determine the unique number without extra space.

⚙️

Algorithm

4 steps

1Step 1: Initialize two variables, ones and twos, to track the bits seen once and twice.
2Step 2: Iterate through each number in the array, updating ones and twos based on the current number's bits.
3Step 3: Use bitwise operations to ensure that bits that appear three times are cleared from ones and twos.
4Step 4: After processing all numbers, ones will contain the unique number.

solution.py8 lines

1# Full working Python code
2
3def singleNumber(nums):
4    ones, twos = 0, 0
5    for num in nums:
6        ones = (ones ^ num) & ~twos
7        twos = (twos ^ num) & ~ones
8    return ones

ℹ

Complexity note: This complexity is linear because we only pass through the array once, and we use constant space for the variables.

1Using bit manipulation can significantly reduce time complexity.
2Tracking occurrences using bitwise operations is efficient.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.