package main

func singleNumberOld(nums []int) int {
	set := make(map[int]bool, 0)
	sumNums := 0
	for _, v := range nums {
		sumNums += v
		if !set[v] {
			set[v] = true
		}
	}
	sumSet := 0
	for k := range set {
		sumSet += k
	}
	return (sumSet*3 - sumNums) / 2
}

// x2 x1   x2 x1   x2 x1   x2 x1   x2 x1
//  0  0 -> 0  1 -> 1  0 -> 1  1 -> 0  0
// So: x1 ^= i, x2 ^= (x1 & i), ... , xn ^= (x[n-1] & ... & x1 & i)
// And we need a mask to set x1~xn to 0 when counter reaches k,
// which means mask == 0 only when count == k. For example, when k is 3,
// mask = 11, ie. mask = !(x2 & x1)
func singleNumber(nums []int) int {
	x2, x1, mask := 0, 0, 0
	for _, i := range nums {
		x2 ^= (x1 & i)
		x1 ^= i
		mask = ^(x2 & x1)
		x2 &= mask
		x1 &= mask
	}
	return x1
}

// func main() {
// 	println(singleNumber(
// 		[]int{0, 1, 0, 1, 99, 1, 0}))
// }