137. Single Number II

Problem

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

Problem Summary

Given a non-empty integer array, every element appears three times except for one element that appears only once. Find the element that appears only once. The algorithm is required to have linear time complexity and use no extra auxiliary space.

Solution Approach

• This problem is an enhanced version of problem 136. This type of problem can also be extended: in an array where every element appears 5 times, find the number that appears only once.
• In this problem, we are required to find the number that appears once, and the numbers that appear 3 times all need to be eliminated. Problem 136 eliminates numbers that appear 2 times. This problem also has a very similar solution: numbers that appear 3 times also need to be eliminated. Define the states 00, 10, and 01, these 3 states. When a number appears 3 times, the number of times 1 appears at each of its bit positions must be a multiple of 3, so after 1 appears 3 times, it is reset to zero and cleared. How can this be achieved? It can be done by imitating ternary (00, 01, 10).
• The variable ones records the number of 1s appearing at each bit during traversal. XOR it with A[i], with the purpose of:
  • If both are 1 at a bit, it means the historical statistics result ones has appeared once and A[i] has another 1, so it has appeared 2 times and needs to be carried into the twos variable.
  • If the two values at a bit are 0 and 1 respectively, add it to the ones statistics result.
  • Finally, & ^twos is also needed in order to implement ternary behavior, clearing it when it appears 3 times. For example, when ones = x, then twos = 0; when twos = x, then ones = 0;
• The variable twos records the number of bits that have appeared as 1 twice during traversal. The purpose of XORing it with A[i] is the same as described above, so it will not be repeated.

In golang, &^ means AND NOT. Here ^ as a unary operator means bitwise negation (^0001 0100 = 1110 1011). X &^ Y means keeping the bits in X that differ from Y and clearing the bits that are the same.

In golang, there is no ~ bit operation operator as in Java. The ~ operator in Java represents bitwise negation. This operation is equivalent to using the ^ operator in golang as a unary operator.

• First, convert ones -> ones'. By observation, we can see that ones = (ones ^ nums[i]) & ^twos

• Second, convert twos -> twos'. This step needs to use the ones from the previous step. By observation, we can see that twos = (twos ^ nums[i]) & ^ones.

This problem can also be further extended: in an array where every element appears 5 times, find the number that appears only once. How should this be done? The idea is still the same: simulate a base-5 system, and eliminate after 5 occurrences. The code is as follows:

// Solution 1
func singleNumberIII(nums []int) int {
	na, nb, nc := 0, 0, 0
	for i := 0; i < len(nums); i++ {
		nb = nb ^ (nums[i] & na)
		na = (na ^ nums[i]) & ^nc
		nc = nc ^ (nums[i] & ^na & ^nb)
	}
	return na & ^nb & ^nc
}

// Solution 2
func singleNumberIIII(nums []int) int {
	twos, threes, ones := 0xffffffff, 0xffffffff, 0
	for i := 0; i < len(nums); i++ {
		threes = threes ^ (nums[i] & twos)
		twos = (twos ^ nums[i]) & ^ones
		ones = ones ^ (nums[i] & ^twos & ^threes)
	}
	return ones
}

Code

package leetcode

func singleNumberII(nums []int) int {
	ones, twos := 0, 0
	for i := 0; i < len(nums); i++ {
		ones = (ones ^ nums[i]) & ^twos
		twos = (twos ^ nums[i]) & ^ones
	}
	return ones
}

// The following is an extension problem
// In the array, every element appears 5 times; find the number that appears only once.

// Solution 1
func singleNumberIIIII(nums []int) int {
	na, nb, nc := 0, 0, 0
	for i := 0; i < len(nums); i++ {
		nb = nb ^ (nums[i] & na)
		na = (na ^ nums[i]) & ^nc
		nc = nc ^ (nums[i] & ^na & ^nb)
	}
	return na & ^nb & ^nc
}

// Solution 2
func singleNumberIIIII1(nums []int) int {
	twos, threes, ones := 0xffffffff, 0xffffffff, 0
	for i := 0; i < len(nums); i++ {
		threes = threes ^ (nums[i] & twos)
		twos = (twos ^ nums[i]) & ^ones
		ones = ones ^ (nums[i] & ^twos & ^threes)
	}
	return ones
}