#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/two-numbers-appearing-once

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/two-numbers-appearing-once

Repovive

Two Numbers Appearing Once - Bit Manipulation | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Two Numbers Appearing Once

Find two unique elements when others appear twice.

Problem: All appear twice except two numbers. Find both.

$1.$ XOR all → $a \oplus b$

$2.$ Find set bit (differs between $a$ , $b$ )

$3.$ Partition by that bit, XOR each group

xorAll = XOR of all nums
diffBit = xorAll & (-xorAll)
a = b = 0
for num in nums:
    if num & diffBit: a ^= num
    else: b ^= num
return [a, b]

Numbers with same bit cancel in each partition.

Time: $O(n)$ . Space: $O(1)$ .