Single Number Iii

                                            
#include <vector>

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // XOR all numbers to find the XOR of the two single numbers.
        int xorResult = 0;
        for (int num : nums) {
            xorResult ^= num;
        }
        
        // Find the rightmost set bit in the XOR result.
        int rightmostSetBit = 1;
        while ((rightmostSetBit & xorResult) == 0) {
            rightmostSetBit <<= 1;
        }
        
        // Partition the numbers based on the rightmost set bit and XOR them separately.
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if ((num & rightmostSetBit) == 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }
        
        return {num1, num2};
    }
};

                                            
class Solution {
    public int[] singleNumber(int[] nums) {
        int diff = 0;
        for (int num : nums) {
            diff ^= num;
        }
        
        diff &= -diff;
        
        int[] result = new int[2];
        for (int num : nums) {
            if ((num & diff) == 0) {
                result[0] ^= num;
            } else {
                result[1] ^= num;
            }
        }
        
        return result;
    }
}

                                            
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        xor_result = 0
        for num in nums:
            xor_result ^= num
        
        mask = 1
        while mask & xor_result == 0:
            mask <<= 1
        
        num1 = 0
        num2 = 0
        for num in nums:
            if mask & num:
                num1 ^= num
            else:
                num2 ^= num
        
        return [num1, num2]

                                            
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function(nums) {
    let xor = 0;
    for (let num of nums) {
        xor ^= num;
    }
    
    let diff = xor & -xor;
    let result = [0, 0];
    
    for (let num of nums) {
        if ((num & diff) === 0) {
            result[0] ^= num;
        } else {
            result[1] ^= num;
        }
    }
    
    return result;
};

                                            
function singleNumber(nums: number[]): number[] {
    let xor = 0;
    for (const num of nums) {
        xor ^= num;
    }
    
    const diff = xor & -xor;
    let result = [0, 0];
    
    for (const num of nums) {
        if ((num & diff) === 0) {
            result[0] ^= num;
        } else {
            result[1] ^= num;
        }
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function singleNumber($nums) {
        $xor = 0;
        foreach ($nums as $num) {
            $xor ^= $num;
        }
        
        $mask = 1;
        while (($mask & $xor) == 0) {
            $mask <<= 1;
        }
        
        $num1 = 0;
        $num2 = 0;
        
        foreach ($nums as $num) {
            if (($num & $mask) == 0) {
                $num1 ^= $num;
            } else {
                $num2 ^= $num;
            }
        }
        
        return [$num1, $num2];
    }
}

                                            
class Solution {
    func singleNumber(_ nums: [Int]) -> [Int] {
        var xor = 0
        for num in nums {
            xor ^= num
        }
        
        let lowBit = xor & -xor
        
        var result: [Int] = [0, 0]
        
        for num in nums {
            if (num & lowBit) == 0 {
                result[0] ^= num
            } else {
                result[1] ^= num
            }
        }
        
        return result
    }
}

                                            
class Solution {
    fun singleNumber(nums: IntArray): IntArray {
        var diff = 0
        for (num in nums) {
            diff = diff.xor(num)
        }
        
        diff = diff.and(-diff)
        
        var result = intArrayOf(0, 0)
        for (num in nums) {
            if ((num and diff) == 0) {
                result[0] = result[0].xor(num)
            } else {
                result[1] = result[1].xor(num)
            }
        }
        
        return result
    }
}

                                            
class Solution {
  List<int> singleNumber(List<int> nums) {
    int xorResult = 0;
    for (int num in nums) {
      xorResult ^= num;
    }
    
    int mask = 1;
    while ((xorResult & mask) == 0) {
      mask <<= 1;
    }
    
    int num1 = 0, num2 = 0;
    for (int num in nums) {
      if ((num & mask) == 0) {
        num1 ^= num;
      } else {
        num2 ^= num;
      }
    }
    
    return [num1, num2];
  }
}

                                            
func singleNumber(nums []int) []int {
    xor := 0
    for _, num := range nums {
        xor ^= num
    }
    diff := xor & (-xor)
    res := make([]int, 2)
    for _, num := range nums {
        if (num & diff) == 0 {
            res[0] ^= num
        } else {
            res[1] ^= num
        }
    }
    return res
}

                                            
# @param {Integer[]} nums
# @return {Integer[]}
def single_number(nums)
    xor = 0
    for num in nums
        xor ^= num
    end
    
    mask = 1
    while (xor & mask) == 0
        mask <<= 1
    end
    
    a = 0
    b = 0
    for num in nums
        if (num & mask) == 0
            a ^= num
        else
            b ^= num
        end
    end
    
    return [a, b]
end

                                            
object Solution {
    def singleNumber(nums: Array[Int]): Array[Int] = {
        val xorOfTwoNums = nums.reduce(_ ^ _)
        val diffBit = xorOfTwoNums & (-xorOfTwoNums)
        var res = Array(0, 0)
        
        for (num <- nums) {
            if ((num & diffBit) == 0) {
                res(0) ^= num
            } else {
                res(1) ^= num
            }
        }
        
        res
    }
}

                                            
impl Solution {
    pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
        let mut xor = 0;
        for &num in &nums {
            xor ^= num;
        }
        
        let rightmost_set_bit = xor & -xor;
        let mut res = vec![0; 2];
        
        for &num in &nums {
            if (num & rightmost_set_bit) == 0 {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        
        res
    }
}

                                            
-spec single_number(Nums :: [integer()]) -> [integer()].
single_number(Nums) ->
    {A, B} = lists:foldl(
        fun(X, {A, B}) ->
            {A bxor X, B}
        end, {0, 0}, Nums),
    
    Mask = A band (-A),
    
    {Res1, Res2} = lists:foldl(
        fun(X, {A, B}) ->
            if X band Mask =:= 0 -> {A bxor X, B};
               true -> {A, B bxor X}
            end
        end, {0, 0}, Nums),
    
    [Res1, Res2].

To solve this coding challenge, the goal is to identify two unique numbers in an array where all other numbers appear exactly twice, in linear time complexity and using constant extra space.

Explanation

To achieve this, we can leverage the properties of the XOR bitwise operator, which has some useful characteristics for identifying unique numbers in a set of pairs:

XOR of a number with itself is zero, i.e.,
a ^ a = 0

.
XOR of a number with zero is the number itself, i.e.,
a ^ 0 = a

.
XOR is commutative and associative:
a ^ b ^ a = b

.

These properties help us to cancel out all numbers that appear in pairs, leaving only the XOR of the two unique numbers.

Method to Find the Two Unique Numbers:

XOR All Numbers: XOR all elements in the array. Since all numbers that appear twice will cancel out to zero, the result will be the XOR of the two unique numbers (
result

=
num1 ^ num2

).
Identify Rightmost Set Bit: Find a bit that is set to
1

in the XOR result. This bit is different between the two unique numbers.
Divide and Conquer: Using this bit, divide the array elements into two groups:

One group with the bit set.
One group with the bit not set.

Each group will have one unique number and all other numbers appearing in pairs, allowing us to apply XOR again within these subgroups to find the unique elements.

Detailed Steps in Pseudocode:

Below is step-by-step pseudocode detailing every part with comments explaining each step:

Initialize Variables:

                                            
# Initialize a variable to hold XOR result of all numbers
xor_result = 0

XOR All Numbers:

                                            
# Step through each number in nums
for each number in nums:
# XOR current number with xor_result
xor_result = xor_result XOR number

Find Rightmost Set Bit:

                                            
# Initialize a mask to find the rightmost set bit (1)
mask = 1

# Loop to find the first set bit in xor_result
while (mask AND xor_result) == 0:
# Shift mask left by 1 to check the next bit
mask = mask LEFT SHIFT 1

Divide into Two Groups and Find Unique Numbers:

                                            
# Initialize the two unique numbers to 0
unique_number1 = 0
unique_number2 = 0

# Step through each number in nums
for each number in nums:
# Check if current number matches the set bit in mask
if (mask AND number) != 0:
# XOR with the first unique number
unique_number1 = unique_number1 XOR number
else:
# XOR with the second unique number
unique_number2 = unique_number2 XOR number

Return the Two Unique Numbers:

                                            
# Return the result as a pair in a list
return [unique_number1, unique_number2]

Putting it all together in a flowing pseudocode:

                                            
# Step 1: Initialize xor_result to 0
xor_result = 0

# Step 2: XOR all numbers in the list
for each number in nums:
    xor_result = xor_result XOR number

# Step 3: Find the rightmost set bit in xor_result
mask = 1
while (mask AND xor_result) == 0:
    mask = mask LEFT SHIFT 1

# Step 4: Initialize two unique numbers to 0
unique_number1 = 0
unique_number2 = 0

# Step 5: Divide numbers into two groups and XOR within each group
for each number in nums:
    if (mask AND number) != 0:
        unique_number1 = unique_number1 XOR number
    else:
        unique_number2 = unique_number2 XOR number

# Step 6: Return the two unique numbers
return [unique_number1, unique_number2]

This pseudocode effectively captures the logic for finding the two unique numbers in an array using bitwise XOR operations and separation based on a distinguishing set bit, achieving both linear runtime complexity and constant space usage.