We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Single Number II

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires identifying a unique number in an array where all other numbers appear thrice.
  • A naive approach using a hash map would not meet the constant space requirement.
  • Bit manipulation can be leveraged to count the occurrences of bits in the numbers.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use bit manipulation. The idea is to count the number of times each bit (from the least significant to the most significant) appears across all numbers in the array. Since every number except one appears three times, the bits corresponding to numbers that appear three times will contribute to a count that is a multiple of three. The bits from the unique number will cause the count to differ from a multiple of three.

  1. We will create an array of size 32 (for each bit in a 32-bit integer) to count the occurrences of each bit.
  2. For each number, we will iterate through each bit and update our counts.
  3. After processing all numbers, we will check each bit count. If a count is not a multiple of three, it means that bit is set in the unique number.
  4. Finally, we will reconstruct the unique number from the bits that were found.

Code Solutions

def singleNumber(nums):
    count = [0] * 32  # To count bits for each of the 32 positions
    for num in nums:
        for i in range(32):
            count[i] += (num >> i) & 1  # Count the bits in each position

    result = 0
    for i in range(32):
        if count[i] % 3:  # If count is not a multiple of 3
            result |= (1 << i)  # Set the bit in the result

    # Handle negative numbers
    if count[31] % 3:  # Check if the sign bit is set
        result -= (1 << 32)

    return result
← Back to All Questions