LeetCode Problem Link

Approach - 1 || Brute Force Approach

Approach:

1. We use a HashMap to store the frequency of each number in the array.

2. We iterate through the array once to populate the HashMap.

3. Then, we iterate through the array again and check for each number if its frequency is less than 2.

4. If the frequency is less than 2, we add that number to the result array.

5. Finally, we return the result array containing the two numbers that appear only once.

// Java Code
class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> mp = new HashMap<>();
        int[] arr = new int[2];
        int ind = 0;
        for(int i : nums){
            mp.put(i, mp.getOrDefault(i, 0)+1);
        }
        for(int i : nums){
            if(mp.get(i) < 2) arr[ind++] = i;
        }
        return arr;
    }
}

// C++ Code
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> mp;
        vector<int> arr;
        for(int i : nums){
            mp[i]++;
        }
        for(int i : nums){
            if(mp[i] < 2) arr.push_back(i);
        }
        return arr;
    }
};

# Python Code
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        mp = {}
        arr = []
        for i in nums:
            mp[i] = mp.get(i, 0) + 1
        for i in nums:
            if mp[i] < 2:
                arr.append(i)
        return arr

Approach - 2 || Optimal Approach - Bucket Concept

This solution uses a bitwise XOR operation to find the two numbers that appear only once in the given array. Let's break down the approach:

1. Calculate XOR of all elements: In the first loop, the code calculates the bitwise XOR of all elements in the array. This will result in the XOR of the two numbers that appear only once because all other numbers will cancel out due to their pairs.

2. Find the rightmost set bit: The next step is to find the rightmost set bit in the XOR result. This is done by performing the operation (xor & xor-1) ^ xor. This operation flips all the bits after the rightmost set bit. The result is then XORed with the original XOR result to isolate the rightmost set bit.

3. Partition the numbers: Once we have the rightmost set bit, we can use it to partition the numbers into two groups:

   • Group 1 (b0): Numbers having the rightmost bit set.

   • Group 2 (b1): Numbers not having the rightmost bit set.

4. XOR each group individually: Finally, we XOR all the numbers in each group separately. This will give us the two numbers that appear only once.

5. Return the result: The two numbers obtained from the XOR operations are returned as an array.

// Java Code 
class Solution {
    public int[] singleNumber(int[] nums) {
        long xor = 0;
        for(int i : nums) xor ^= i;
        // find the rightmost set bit
        long rightmost = (xor & xor-1)^xor;
        int b0 = 0;
        int b1 = 0;
        for(int i : nums){
            if((i & rightmost) != 0) b0 ^= i;
            else b1 ^= i;
        }
        return new int[]{b0, b1};
    }
}

// C++ Code
class Solution {
public:
    std::vector<int> singleNumber(std::vector<int>& nums) {
        long xor_result = 0;
        for (int num : nums) xor_result ^= num;

        // Find the rightmost set bit
        long rightmost = (xor_result & (xor_result - 1)) ^ xor_result;

        int b0 = 0, b1 = 0;
        for (int num : nums) {
            if (num & rightmost) b0 ^= num;
            else b1 ^= num;
        }

        return {b0, b1};
    }
};

# Python Code
from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_result = 0
        for num in nums:
            xor_result ^= num

        # Find the rightmost set bit
        rightmost = (xor_result & (xor_result - 1)) ^ xor_result

        b0, b1 = 0, 0
        for num in nums:
            if num & rightmost:
                b0 ^= num
            else:
                b1 ^= num

        return [b0, b1]

That's it !
Thanks for the reading the entire blog.

Connect me on X - @DexterIfti