Find Two Numbers That Appear Only Once

Find Two Numbers That Appear Only Once

Problem Description
In an integer array, except for two numbers, all other numbers appear twice. Please find these two numbers that appear only once. The time complexity should be O(n), and the space complexity should be O(1).

Solution Approach
This problem is an extension of the classic single-number problem. If there was only one number appearing once, we could solve it directly using the XOR operation. However, since there are two distinct numbers here, we need to break down the problem.

Step-by-Step Breakdown

  1. Overall XOR to Obtain Key Information
    First, perform the XOR operation on all numbers in the array. Since identical numbers XOR to 0, the final result equals the XOR value of the two target numbers (let's call them a and b):
    xor_all = a ^ b
    This result is not 0 (because a ≠ b), so there is at least one binary bit that is 1.

  2. Find the Bit That Distinguishes a and b
    Choose any binary bit that is 1 in xor_all (usually the lowest 1 bit). This bit indicates that a and b differ at this bit (one is 0, the other is 1).
    For example, if xor_all = 6 (binary 110), the lowest 1 bit is at the second position (counting from right to left, starting from 0). We can use this bit to divide the array into two groups.

  3. Group XOR
    According to the selected binary bit, divide the array into two groups:

    • Numbers with this bit as 0
    • Numbers with this bit as 1
      Since a and b differ at this bit, they must be placed into different groups. Meanwhile, identical numbers will be placed into the same group.
      Perform XOR operations on each group separately. The result from each group will be one of the target numbers.

Example Illustration
Array: [1, 2, 1, 3, 2, 5]

  1. Overall XOR: 1^2^1^3^2^5 = 3^5 = 6 (binary 110)
  2. Select the lowest 1 bit (second position) and use it for grouping:
    • Second bit is 0: 1(001), 1(001), 5(101) → XOR result: 1^1^5 = 5
    • Second bit is 1: 2(010), 3(011), 2(010) → XOR result: 2^3^2 = 3
  3. Result: 3 and 5

Key Points

  • Utilize XOR properties: identical numbers XOR to 0, while XOR of different numbers can reveal differing bits.
  • Grouping via the differing bit transforms the problem into two single-number problems.
  • Space complexity is O(1), using only a few variables.