Single Number III

1class Solution {
2    public int[] singleNumber(int[] nums) {
3        // Step 1: XOR all numbers
4        int xor = 0;
5        for (int num : nums) {
6            xor ^= num;
7        }
8
9        // Step 2: Find rightmost set bit
10        int diff = xor & (-xor);
11
12        // Step 3: Separate into two groups and XOR
13        int[] result = new int[2];
14        for (int num : nums) {
15            if ((num & diff) == 0) {
16                result[0] ^= num; // Group 0
17            } else {
18                result[1] ^= num; // Group 1
19            }
20        }
21
22        return result;
23    }
24}