algoadvance

Given an integer array nums, where 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.

Example:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]

Clarifying Questions

1. Q: Can the input array be empty?
   • A: No, according to the problem, the input array will always have at least 2 numbers that appear once.
2. Q: Are the numbers in nums guaranteed to be integers?
   • A: Yes, the numbers in the input array are integers.
3. Q: What if the input length is very large?
   • A: The solution should seek to maintain a linear time complexity and constant space complexity where possible.
4. Q: Can there be duplicates beside those specified? A: No, each number will appear exactly twice, with the exception of the two numbers that appear only once.

Strategy

1. XOR Operation:
   • Utilize the property of XOR (Exclusive OR) to identify the two unique numbers. XOR-ing all numbers will cancel out the numbers that appear twice, resulting in the XOR of the two unique numbers.
2. Identify a Set Bit:
   • Find a bit that is set (i.e., 1) in the result of the XOR from step 1. This bit guarantees that the two unique numbers differ at that position.
3. Partition and XOR:
   • Use the set bit to partition the input numbers into two groups. One group will have the numbers with that bit set, and the other group will have numbers with the bit not set.
   • XOR the numbers in each group separately to find the two unique numbers.

Code

def singleNumber(nums):
    # Step 1: XOR all numbers to get the XOR of the two unique numbers
    xor = 0
    for num in nums:
        xor ^= num
    
    # Step 2: Find a set bit in the xor (rightmost set bit)
    set_bit = xor & -xor
    
    # Step 3: Partitioning numbers and XOR-ing separately
    num1, num2 = 0, 0
    for num in nums:
        if num & set_bit:
            num1 ^= num
        else:
            num2 ^= num
    
    return [num1, num2]

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

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the input array. Each step involves either a single pass or constant time operations.
• Space Complexity: O(1), the algorithm uses a constant amount of extra space independent of the input size.

This approach leverages the power of bit manipulation effectively to maintain linear time complexity, which is optimal for this problem.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?