algoadvance

LeetCode 137 - Single Number II:

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

Clarifying Questions

  1. What is the range of values that can be contained in the array?
    • The values can be any integer within the standard limits of a 32-bit signed integer.
  2. Can the array be empty?
    • No, the array will have at least one element.
  3. Can the input contain negative numbers?
    • Yes, the input array can contain negative numbers.

Strategy

To solve this problem, we need to use bit manipulation to ensure both linear runtime and constant space complexity. Here’s the thought process:

  1. We’ll use two variables to keep track of the bits occurring in the input list: ones and twos.
  2. ones will store the bits which have appeared exactly once.
  3. twos will store the bits which have appeared exactly twice.
  4. When a bit appears the third time, it will be reset from ones and twos.

By the end of the traversal, ones will contain the bits of the number that appears exactly once.

Code

def singleNumber(nums):
    # Initialize two variables to store the bits
    ones, twos = 0, 0

    for num in nums:
        # First appearance:
        # Add num to 'ones' if it is not there in 'twos'
        ones = (ones ^ num) & ~twos
        
        # Second appearance:
        # Add num to 'twos' if it is not there in 'ones'
        twos = (twos ^ num) & ~ones

    return ones

# Example usage
nums = [2, 2, 3, 2]
print(singleNumber(nums))  # Output: 3

Explanation of Code

  1. Initialization:
    • ones, twos are initialized to 0.
  2. Loop through each number in the array:
    • For each number (num):
      • Update ones only if the current number is not already in twos. This ensures that ones holds bits for numbers appearing the first time.
      • Update twos only if the current number is not already in ones. This ensures that twos holds bits for numbers appearing the second time.
  3. Return ones:
    • After processing all numbers, ones will hold the bits of the number that appears exactly once in the array.

Time Complexity

This solution ensures both the required linear runtime and constant extra space usage.

Try our interview co-pilot at AlgoAdvance.com