Leetcode #137 Solution Explaination

Goal

Find the only number that appears exactly ONCE while others appear three times in O(N) time and O(1) space complexity.

https://leetcode.com/problems/single-number-ii

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
    once=twice=0

    for num in nums:
        once=(once^num) & (~twice)
        twice=(twice^num) & (~once)
    return once

First, we have to know what ^ ,~ and & mean in bitwise operation:

^: XOR (exclusive OR) operation - Toggles the bits that are different between the two numbers, in other words

1. if num NOT in once → Add num to once

2. if num in once → Remove num from once

nums = [3,52,52]
once = 0
for num in nums:
    once = (num^once)

1st: num = 3, once = 0 -> once includes 3
3 | 11
0 | 00
------
3 | 11

2nd: num = 52, once = 3 -> once includes 3,52
52 | 110100
 3 | 000011
-----------
55 | 110111

3rd: num = 52, once = 55 -> once removes 52, includes 3
52 | 110100
55 | 110111
-----------
 3 | 000011

the final once will be 3

~ : NOT operation - Flip all the bits of twice → ~twice representing all num NOT in twice

 3 | 00000011
-------------
~3 | 11111100

& : AND operation - Results in 1 only when both operands have a corresponding 1 bit

# 52 & 12 = 8    

52 | 110100
12 | 001100
-----------
 8 | 000100

(a^b) & (~c) : (a XOR b) AND (NOT c)

nums=[2,2,3,2]

once=twice=0
for num in nums:
    once=(once^num) & (~twice)
    twice=(twice^num) & (~once)

1st loop: once=0, num=2, twice=0

# once^num = 2
2 | 10
0 | 00
------
2 | 10

# ~twice = 3
0 | 00
------
3 | 11

# (once^num) & (~twice)
# 2 & 3 = 2

2 | 10
3 | 11
------
2 | 10

### once will include num(2) because 2 is not included yet

================================================
# twice ^ num = 2
0 | 00
2 | 10
---
2 | 10

# ~once = 1
2 | 10
------
1 | 01

# (twice ^ num) & (~once)
# 2 & 1 = 0
2 | 10
1 | 01
------
0 | 00

### twice won't include num(2) because once already includes it

When a number appears

1. the first time: add to once

2. the second time: remove from once and add to twice

3. the third time: remove from twice and won't add to once because of ~twice

This process is repeated for each element in nums, updating the once and twice variables accordingly. At the end, the value of once will represent the unique number that appears exactly once in the list.