260. Single Number III – Leetcode Solutions

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # Step 1: XOR all the numbers together. The result will be the XOR of the two unique numbers.
        xor_result = 0
        for num in nums:
            xor_result ^= num
        
        # Step 2: Find the rightmost set bit in the xor_result (i.e., where the two unique numbers differ)
        # This helps in dividing the numbers into two groups.
        rightmost_bit = xor_result & -xor_result
        
        # Step 3: Use the rightmost bit to partition numbers into two groups and XOR them separately
        # One group will have one of the unique numbers and the other group will have the other unique number.
        num1, num2 = 0, 0
        for num in nums:
            if num & rightmost_bit:
                num1 ^= num
            else:
                num2 ^= num
        
        # Return the two unique numbers
        return [num1, num2]

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> countMap;

        // Step 1: Count occurrences of each number
        for (int num : nums) {
            countMap[num]++;
        }

        // Step 2: Find the two numbers that appear only once
        vector<int> result;
        for (const auto& entry : countMap) {
            if (entry.second == 1) {
                result.push_back(entry.first);
            }
        }

        return result;
    }
};

var singleNumber = function(nums) {
    // Step 1: Initialize xorSum to 0
    let xorSum = 0;

    // Step 2: XOR all numbers in the array
    for (let num of nums) {
        xorSum ^= num;  // This will result in the XOR of the two unique numbers
    }

    // Step 3: Find the rightmost set bit in xorSum
    // We use the expression xorSum & (-xorSum) to isolate the rightmost set bit
    const diffBit = xorSum & -xorSum;

    // Step 4: Initialize variables for the two unique numbers
    let x = 0, y = 0;

    // Step 5: Divide numbers into two groups based on the diffBit and XOR within the groups
    for (let num of nums) {
        if (num & diffBit) {
            x ^= num;  // XOR numbers where the diffBit is set
        } else {
            y ^= num;  // XOR numbers where the diffBit is not set
        }
    }

    // Step 6: Return the two unique numbers in an array
    return [x, y];
};

class Solution {
    public int[] singleNumber(int[] nums) {
        // Step 1: Initialize xorSum to 0
        int xorSum = 0;

        // Step 2: XOR all numbers in the array
        for (int num : nums) {
            xorSum ^= num;  // This will result in the XOR of the two unique numbers
        }

        // Step 3: Find the rightmost set bit in xorSum
        // We use the expression xorSum & -xorSum to isolate the rightmost set bit
        int diffBit = xorSum & -xorSum;

        // Step 4: Initialize variables for the two unique numbers
        int x = 0, y = 0;

        // Step 5: Divide numbers into two groups based on the diffBit and XOR within the groups
        for (int num : nums) {
            if ((num & diffBit) != 0) {
                x ^= num;  // XOR numbers where the diffBit is set
            } else {
                y ^= num;  // XOR numbers where the diffBit is not set
            }
        }

        // Step 6: Return the two unique numbers in an array
        return new int[] { x, y };
    }
}