#137

Medium

LeetCode Problem Workspace

Single Number II

Find the single element in an array where every other element appears three times, using bit manipulation and constant space.

array bit manipulation

Problem Statement

Given an array of integers where every element appears exactly three times except for one, which appears once, your task is to find that unique element. You are required to implement a solution that works in linear time and uses constant extra space.

Your solution should avoid using hashmaps or other space-intensive data structures, relying instead on bit manipulation to efficiently find the unique number in the array.

Examples

Example 1

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

Output: 3

Example details omitted.

Example 2

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

Output: 99

Example details omitted.

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.

Solution Approach

Bitwise XOR and AND

The most efficient way to approach this problem is to use bitwise operations. We can maintain a counter that tracks the occurrence of bits at each position. By iterating over the array and performing bitwise XOR and AND, we can isolate the unique number. The key idea is that elements appearing three times cancel each other out, leaving the single element.

Tracking Bit Counts

We can track the number of times each bit appears across all elements. Using this method, we count the frequency of bits, and at the end, any bit that appears a multiple of three can be discarded, while the bits of the single number remain.

Constant Space Solution

The algorithm must use constant space, meaning we cannot rely on extra data structures like arrays or hashmaps. This can be achieved by using just a few integer variables to track the current and previous bit occurrences while processing the array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n), where n is the length of the input array, as each element is processed once. The space complexity is O(1), since only a constant number of variables are used to track the bits, and no additional data structures are created.

What Interviewers Usually Probe

Look for an efficient solution using bit manipulation techniques to handle large arrays within time and space constraints.
Candidates should avoid using hashmaps or arrays, focusing instead on bitwise operations to solve the problem.
Pay attention to how well the candidate handles the edge cases and optimizes the solution for constant space usage.

Common Pitfalls or Variants

Common pitfalls

Relying on hashmaps or arrays, which violate the constant space requirement.
Not correctly handling the bitwise operations, leading to incorrect results when tracking occurrences of the bits.
Failing to consider edge cases such as when the array has only one element or all elements are negative.

Follow-up variants

Implementing the solution using a different set of bitwise operations or bit tracking techniques.
Using different approaches like mathematical formulas or recursion instead of bit manipulation.
Handling arrays of varying sizes and input constraints, ensuring the solution works under all edge cases.

FAQ

What is the best approach for solving the Single Number II problem?

The best approach involves using bitwise operations, particularly XOR and AND, to track the occurrence of bits across all numbers. This method ensures constant space usage and linear time complexity.

Can I use extra space to solve the Single Number II problem?

No, the problem specifically requires a solution that uses only constant extra space. Using hashmaps or arrays would violate this constraint.

What if there are multiple unique numbers in the array?

The problem guarantees that only one element will appear once, while all others appear three times. If there were multiple unique numbers, the problem statement would be different.

How does bit manipulation help in solving this problem?

Bit manipulation allows us to track individual bit occurrences across all numbers in the array. By using XOR and AND operations, we can isolate the unique number efficiently.

What edge cases should I consider when solving this problem?

Edge cases include arrays with only one element, arrays with negative numbers, and arrays where the unique number is at the start or end of the array. Make sure your solution handles these scenarios correctly.

terminal

Solution

Solution 1: Bitwise Operation

We can enumerate each binary bit $i$, and for each binary bit, we calculate the sum of all numbers on that bit. If the sum of the numbers on that bit can be divided by 3, then the number that only appears once on that bit is 0, otherwise it is 1.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cnt = sum(num >> i & 1 for num in nums)
            if cnt % 3:
                if i == 31:
                    ans -= 1 << i
                else:
                    ans |= 1 << i
        return ans

Solution 2: Digital Circuit

We can use a more efficient method that uses digital circuits to simulate the above bitwise operation.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cnt = sum(num >> i & 1 for num in nums)
            if cnt % 3:
                if i == 31:
                    ans -= 1 << i
                else:
                    ans |= 1 << i
        return ans

Solution 3: Set + Math

#### TypeScript

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cnt = sum(num >> i & 1 for num in nums)
            if cnt % 3:
                if i == 31:
                    ans -= 1 << i
                else:
                    ans |= 1 << i
        return ans

Solution 4: Bit Manipulation

#### TypeScript

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cnt = sum(num >> i & 1 for num in nums)
            if cnt % 3:
                if i == 31:
                    ans -= 1 << i
                else:
                    ans |= 1 << i
        return ans

Continue Practicing

#136 single number #90 subsets ii #78 subsets