Single Number III

Problem Statement

In this task, you are given an integer array named nums. This array has an interesting property: exactly two elements in the array appear only once while all other elements appear exactly twice. Your goal is to identify these two unique elements. The solution should be efficient—ideally with a linear runtime complexity and using only constant extra space—and you can return the result in any order. This problem tests your ability to manipulate and process arrays under specific constraints, engaging with concepts such as bit manipulation for optimal solutions.

Examples

Example 1

Input:

nums = [1,2,1,3,2,5]

Output:

[3,5]

Explanation:

[5, 3] is also a valid answer.

Example 2

Input:

nums = [-1,0]

Output:

[-1,0]

Example 3

Input:

nums = [0,1]

Output:

[1,0]

Constraints

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Each integer in nums will appear twice, only two integers will appear once.

Approach and Intuition

To solve the problem while adhering to the constraints of linear runtime complexity and constant space complexity, one can harness the properties of XOR (exclusive OR) operations. Here's an intuitive breakdown:

1. XOR for distinction: XOR all elements in the array together. Numbers that appear twice will cancel out due to the XOR property (a ^ a = 0), leaving the XOR of the two unique numbers.

2. Identify non-overlapping groups: Since the two unique numbers are different, there must be at least one bit position at which the two numbers differ (where one has a bit set to 1 and the other to 0). Find this bit by looking for the rightmost set bit (1) in the result of the XOR operation performed in the previous step. This can be done using x & -x.

3. Separate into two groups using the identified bit: Once a differing bit is identified, use it to split all numbers into two groups—one group with this bit set and the other with this bit not set. The unique numbers will fall into separate groups due to their differing bits.

4. XOR within groups to find unique numbers: Perform XOR operation separately on each group. All numbers appearing twice will cancel each other out, and the result for each group will be one of the two unique numbers.

This approach cleverly leverages bit manipulation to retain a lower complexity while avoiding the use of extra space, beyond the variables used to keep track of the groups and results.

Solutions

class Solution {
  public int[] findTwoSingleNumbers(int[] array) {
    int xorAll = 0;
    for (int value : array) xorAll ^= value;

    int uniqueBit = xorAll & (-xorAll);

    int singleOne = 0;
    for (int value : array) if ((value & uniqueBit) != 0) singleOne ^= value;

    return new int[]{singleOne, xorAll^singleOne};
  }
}