[LeetCode] 260. Single Number III

 Problem : https://leetcode.com/problems/single-number-iii/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        return [x[0] for x in filter(lambda x: x[1] == 1, Counter(nums).items())]

Sort first then count numbers solution:

Time complexity = O ( N * LogN )

Space complexity = O ( 1 )

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        nums.sort()
        
        a = cntA = 0
        b = cntB = 0
        
        for n in nums:
            if cntA == 0:
                a = n
                cntA += 1
            elif a == n:
                cntA -= 1
            elif cntB == 0:
                b = n
                cntB += 1
            elif b == n:
                cntB -= 1
        
        
        return [a, b]

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

class Solution {
    public int[] singleNumber(int[] nums) {
        // Since all numbers except A and B appear twice
        // XOR = A ^ B
        int XOR = 0;
        for (int n : nums) {
            XOR ^= n;
        }
        
        // Find the first bit of the XOR from the right where bit == 1.
        // Because XR = A ^ B, this bit is either contribute by A or B.
        int offset = 0;
        while (offset < 32 && (XOR & (1 << offset)) == 0 ) {
            offset += 1;
        }
                
        // Use the bit of 'offset' as a flag to separate the original numbers to 2 groups
        // Group 1 : A, other numbers except B
        // Group 2 : B, other numbers except A
        // A = accumulated xor of numbers in group 1 
        // B = accumulated xor of number in group 2
        int A = 0, B = 0;
        for (int n : nums) {
            if ((n & (1 << offset)) != 0) {
                A ^= n;
            } else {
                B ^= n;
            }
        }
        
        return new int[] {A, B};
    }
}

Assume A and B are the 2 single numbers. Because all other numbers appear exactly twice. 

xor all numbers  =  A ^ B.

Then find the first bit of A ^ B = 1.   This bit is either from A or from B.

Use this bit to split the nums into 2 groups. Group 1 includes A and all other numbers except B. Group 2 includes B and all other numbers except A.

Since in each group there is only one single number,  result of xor all numbers in the group equals to the single number.

Edited on 11/07/2021. Update bit manipulation solution.

Edited on 05/31/2024. Update bit manipulation solution.