Single Number III
Solve this Problema ^ b rather than a clean answer on its own. The fix is to find one bit where a and b must disagree (any bit set in a ^ b works), and use it to split every number into two groups — XOR-ing each group separately then isolates one single per group.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ nums.length ≤ 3 × 10⁴ - ◆
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴ - ◆
Exactly two values in nums appear exactly once; every other value appears exactly twice
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Hashmap Counting
GoodCount how many times each value occurs, then collect every entry whose count is 1 — there will be exactly two of them. Simple and correct, but it needs a map sized to the number of distinct values in the array.
O(n)O(n)1class Solution {
2 public int[] singleNumber(int[] nums) {
3 Map<Integer, Integer> freq = new HashMap<>();
4 for (int num : nums) {
5 freq.put(num, freq.getOrDefault(num, 0) + 1);
6 }
7 int[] result = new int[2];
8 int idx = 0;
9 for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
10 if (entry.getValue() == 1) {
11 result[idx++] = entry.getKey();
12 }
13 }
14 return result;
15 }
16}Optimal — XOR Partition by Differing Bit
OptimalXOR every element together first. Every paired value cancels, so what's left is a ^ b — the XOR of exactly the two single values. Since a ≠ b, that result is non-zero, so it has at least one set bit; pick out its lowest set bit as a splitting rule. a and b must disagree at that bit (that's exactly what a set bit in a ^ b means), so they land in different groups when every number is split by whether it has that bit set — and every paired value, being identical to its twin, always lands in the SAME group as its twin. XOR-ing each group separately cancels every remaining pair, isolating a in one group and b in the other.
O(n)O(1)1class Solution {
2 public int[] singleNumber(int[] nums) {
3 int xorAll = 0;
4 for (int num : nums) {
5 xorAll ^= num;
6 }
7 int diffBit = xorAll & (-xorAll);
8 int a = 0, b = 0;
9 for (int num : nums) {
10 if ((num & diffBit) != 0) {
11 a ^= num;
12 } else {
13 b ^= num;
14 }
15 }
16 return new int[]{a, b};
17 }
18}