This problem was asked by Google. Given an array of integers where every integer occurs three times except for one integer, which only occurs once, find and return the non-duplicated integer. For example, given [6, 1, 3, 3, 3, 6, 6], return 1. Given [13, 19, 13, 13], return 19. Do this in O(N) time and O(1) space.

main.go

package main

import (
    "fmt"
)


func main() {
    d := []int{10, 20, 10, 30, 10, 30, 30}
    fmt.Println(SingleNumber(d))
}

// SingleNumber function takes in a slice of int
// returns an integer result
func SingleNumber(arr []int) int {
	ones, twos, n := 0, 0, len(arr)

	for i := 0; i < n; i++ {
        twos = twos | (ones & arr[i])
        ones = ones ^ arr[i] 
        commonBitMask := ^(ones & twos)  
        ones &= commonBitMask  
        twos &= commonBitMask
	}
	return ones
}

main.py

# SingleNumber method takes in an array of integers
# returns an integer result
def SingleNumber(array: list): 
    ones, twos = 0, 0 
    for x in array:
        ones, twos = (ones ^ x) & ~twos, (ones & x) | (twos & ~x) 
    assert twos == 0 
    return ones 

print(SingleNumber([12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]))