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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Single Number III

Number: 260

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg, Microsoft, Meta

Problem Description

Given an integer array where exactly two elements appear only once and all the other elements appear exactly twice, find the two elements that appear only once. The answer can be returned in any order.

Key Insights

  • XOR of two identical numbers is 0.
  • XOR of all numbers results in the XOR of the two unique numbers.
  • A set bit in the XOR results (xorTotal) indicates a bit position where the two unique numbers differ.
  • Partitioning the array based on this set bit allows isolation of each unique number.

Space and Time Complexity

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

Solution

Use XOR to combine all numbers, which cancels out the pairs and leaves the XOR of the two unique numbers. Identify any set bit in this XOR to differentiate between the two unique numbers. Partition the numbers based on whether they have that bit set and XOR each group separately. The result are the two unique numbers. This approach leverages bit manipulation with constant extra space and a single pass (or two passes) over the input.

Code Solutions

# Python implementation for "Single Number III"
def singleNumber(nums):
    # Step 1: XOR all numbers to get xorTotal = unique1 XOR unique2
    xorTotal = 0
    for num in nums:
        xorTotal ^= num

    # Step 2: Find a set bit (rightmost set bit) in xorTotal
    diff_bit = xorTotal & -xorTotal

    # Step 3: Partition numbers into two groups and XOR separately
    unique1, unique2 = 0, 0
    for num in nums:
        if num & diff_bit:
            unique1 ^= num
        else:
            unique2 ^= num

    return [unique1, unique2]

# Example usage:
# result = singleNumber([1,2,1,3,2,5])
# print(result)  # Output might be [3, 5] or [5, 3]
← Back to All Questions