Chapter 8 - Bitwise Operator problems

Question 1

Single Number III
Given an array of numbers 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.

Example:

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

Answer 1

Take XOR of all the numbers, find the lowest set bit in the result. This tells us about the bit which is not the same between the two single numbers since double numbers will cancel each other.
For example, XOR of 3(011) and 5(101) will be 6 i.e. 110. Here, last bit is 0, means the last bit of both 3 and 5 are same, but the second last bit of XOR as 1 tells that it is different for both 3 and 5

Divide the set of numbers into two different groups, based on the lowest set bit. Numbers with bit at lowest_set_bit index as 0 will go in one group, and 1 into another group.
This will ensure 3 and 5 goes into two different groups.
Now, XOR the two groups separately and we will get 3 and 5 out.

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

    lowest_set_bit = xor & -xor

    for num in nums:

        if num & lowest_set_bit == 0:
            group1 ^= num 
        else:
            group2 ^= num

    return [group1, group2]

Complexity: O(n) and O(1) -> time and space