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 III

Difficulty: Medium

Problem Description

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

Key Insights

  • Use bit manipulation to efficiently find the two unique numbers.
  • The XOR operation can be used to find the combined effect of all numbers, where duplicate numbers cancel each other out.
  • The result of XORing all numbers provides a number that is a combination of the two unique numbers.
  • By finding a bit that differentiates the two unique numbers, we can separate them into different groups.

Space and Time Complexity

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

Solution

The solution uses the XOR bit manipulation technique. First, we XOR all elements in the array to get a combined result that represents the two unique numbers. Then, we find a bit that is set in this result, which helps us to distinguish between the two unique numbers. Finally, we group the numbers based on this bit and XOR them separately to get the two unique numbers.

Code Solutions

def singleNumber(nums):
    xor_result = 0
    for num in nums:
        xor_result ^= num  # Get the XOR of all numbers
    
    # Find a bit that is set in xor_result
    rightmost_set_bit = xor_result & -xor_result
    
    num1, num2 = 0, 0
    for num in nums:
        if num & rightmost_set_bit:  # Group 1
            num1 ^= num
        else:  # Group 2
            num2 ^= num
    
    return [num1, num2]
← Back to All Questions