Numbers Appearing Only Once

1. Problem Description

In an integer array, every number appears twice except for two numbers. Write a program to find the two numbers that appear only once.

2. Approach

1. Approach 1
   • Map counting
2. Approach 2
   • XOR every element in the array. Since equal elements XOR to 0 and 0 XOR any number gives that number, the final result is the XOR of the two numbers that appear only once
   • Take a bit whose value is 1 and AND it with every number in the array, dividing the array into one group whose result is nonzero and another whose result is zero
   • XOR the two groups separately to obtain the two different numbers that appear once

3. Code

3.1. Map Counting

• java

public class 数组中只出现一次的数字
{
    public static void main(String[] args)
    {
        new 数组中只出现一次的数字().FindNumsAppearOnce(new int[]{2, 4, 3, 6, 3, 2, 5, 5}, new int[]{0}, new int[]{0});
    }

    public void FindNumsAppearOnce(int[] array, int num1[], int num2[])
    {
        // Check parameters
        if (array == null || array.length == 0)
        {
            num1[0] = 0;
            num2[0] = 0;
            return;
        }

        // XOR the array; the result must be the XOR of the two unique numbers
        int xorResult = 0;
        for (int val : array)
        {
            xorResult ^= val;
        }
        // From this result, select a bit whose value is 1
        int bit = 1;
        for (int i = 0; i < 32; i++)
        {
            if ((xorResult & bit) != 0)
            {
                break;
            }
            bit <<= 1;
        }
        // Traverse the array and AND each value with bit, dividing it into groups whose results are zero and nonzero
        List<Integer> arrays1 = new LinkedList<>();
        List<Integer> arrays2 = new LinkedList<>();

        for (int val : array)
        {
            if ((val & bit) == 0)
            {
                arrays1.add(val);
            }
            else
            {
                arrays2.add(val);
            }
        }

        // XOR the two groups separately to obtain the results
        int n1 = 0;
        for (Integer val : arrays1)
        {
            n1 ^= val;
        }

        int n2 = 0;
        for (Integer val : arrays2)
        {
            n2 ^= val;
        }

        num1[0] = n1;
        num2[0] = n2;
    }
}

• go

// Time: O(N)
// Space: O(N)
func FindNumsAppearOnce(nums []int) []int {
	count := make(map[int]int, 0)
	for _, num := range nums {
		count[num]++
	}

	res := make([]int, 0)
	for _, num := range nums {
		if count[num] == 1 {
			res = append(res, num)
		}
	}

	return res
}

3.2. XOR

// Time: O(N)
// Space: O(1)
func FindNumsAppearOnce2(nums []int) []int {
	if len(nums) == 0 {
		return nil
	}

	xorRes := 0
	for _, num := range nums {
		xorRes = xorRes ^ num
	}

	bit := 1
	for i := 0; i < 32; i++ {
		if xorRes&bit != 0 {
			break
		}
		bit = bit << 1
	}

	val1 := 0
	val2 := 0
	for _, num := range nums {
		if num&bit == 0 {
			val1 = val1 ^ num
		} else {
			val2 = val2 ^ num
		}
	}

	res := make([]int, 0)
	res = append(res, val1)
	res = append(res, val2)

	return res
}

4. References

• Numbers That Appear Once - NowCoder
• 136. Single Number - LeetCode