algoadvance

Leetcode 260. Single Number III

Problem Statement

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 need to implement a function in C++ that returns these two unique numbers.

Clarifying Questions

  1. Q: What should be the return type of the function? A: The function should return a vector of integers containing the two unique numbers.

  2. Q: Can the given array have negative numbers? A: Yes, the array can contain negative numbers.

  3. Q: Is the array length restricted to any specific range? A: There are no specific constraints given, but typically the array length will be within practical limits for a coding interview problem.

Strategy

  1. Bit Manipulation: XOR Technique
    • XOR of all elements in nums will result in the XOR of the two unique numbers because all paired numbers will cancel themselves out (XOR of a number with itself is 0).
    • Let the result of XORing these two unique numbers be called xor2. xor2 is effectively a ^ b where a and b are the unique numbers.
  2. Finding a Differentiating Bit
    • Find any bit that is set (1) in xor2. This can be used to differentiate between the two unique numbers because they have different bits at some position.
    • Use this bit to partition all numbers in nums into two groups: one with the differentiating bit set and the other with this bit not set.
  3. Extracting the Unique Numbers
    • XOR all numbers in each group independently. This process will isolate the two unique numbers because all duplicates will cancel out within each group.

Code

#include <vector>
#include <iostream>

std::vector<int> singleNumber(std::vector<int>& nums) {
    // Step 1: Find the XOR of the two unique numbers (a ^ b)
    int xor2 = 0;
    for (int num : nums) {
        xor2 ^= num;
    }
    
    // Step 2: Find a differentiating bit (rightmost set bit)
    int diffBit = xor2 & (-xor2);
    
    // Step 3: Divide numbers into two groups and find the unique numbers
    int num1 = 0, num2 = 0;
    for (int num : nums) {
        if ((num & diffBit) == 0) {
            // Group where the bit is not set
            num1 ^= num;
        } else {
            // Group where the bit is set
            num2 ^= num;
        }
    }
    
    return {num1, num2};
}

// Example usage
int main() {
    std::vector<int> nums = {1, 2, 1, 3, 2, 5};
    std::vector<int> result = singleNumber(nums);
    std::cout << "The two unique numbers are: " << result[0] << " and " << result[1] << std::endl;
    return 0;
}

Time Complexity

The time complexity of the solution is O(n), where n is the number of elements in the array:

Thus, the overall time complexity is linear in terms of the number of elements in the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI