Find the two non-repeating elements in an array of repeating elements

Problem Statement

Given an array where every element appears twice except for two elements which appear only once, find those two non-repeating elements.

Example:

Noob-Friendly Explanation

Imagine you're at a party where everyone is supposed to come in pairs (twins). But two people came alone — they don't have a twin at the party. Your job is to find those two solo people.

One cool trick with numbers: if you XOR a number with itself, you get 0 (they cancel out). So if you XOR all the numbers, all the pairs cancel out and you're left with the XOR of the two unique numbers. But how do you separate them? You find a bit where they differ, and split the array into two groups based on that bit. Each group will have exactly one unique number!

Approach 1: Brute Force

Intuition

For each element, count how many times it appears. If it appears only once, it's one of our answers.

Algorithm

1. For each element, scan the entire array to count occurrences
2. If count == 1, add it to the result
3. Return the two elements with count 1

import java.util.*;

class Solution {
    public static int[] findTwoNonRepeating(int[] arr) {
        int[] result = new int[2];
        int idx = 0;

        for (int i = 0; i < arr.length; i++) {
            int count = 0;
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                }
            }
            if (count == 1) {
                result[idx++] = arr[i];
                if (idx == 2) break;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 7, 9, 2, 4};
        int[] result = findTwoNonRepeating(arr);
        System.out.println(result[0] + ", " + result[1]); // 7, 9
    }
}

Complexity Analysis

• Time Complexity: O(N^2) — For each element, we scan the entire array
• Space Complexity: O(1) — Only using a small result array

Approach 2: Optimal (XOR Trick)

Intuition

1. XOR all elements → gives xor of the two unique numbers (a ^ b)
2. Find any set bit in the XOR result (this bit is different between a and b)
3. Split all numbers into two groups based on that bit
4. XOR within each group → each group gives one unique number

Algorithm

1. XOR all elements to get xorAll = a ^ b
2. Find the rightmost set bit: rightBit = xorAll & (-xorAll)
3. Divide elements into two groups: those with that bit set, and those without
4. XOR within each group to isolate each unique number

import java.util.*;

class Solution {
    public static int[] findTwoNonRepeating(int[] arr) {
        // Step 1: XOR all elements
        int xorAll = 0;
        for (int num : arr) {
            xorAll ^= num;
        }
        // xorAll = a ^ b (where a, b are the two unique numbers)

        // Step 2: Find rightmost set bit
        // This bit is 1 in one unique number and 0 in the other
        int rightmostBit = xorAll & (-xorAll);

        // Step 3: Split into two groups and XOR each group
        int group1 = 0, group2 = 0;
        for (int num : arr) {
            if ((num & rightmostBit) != 0) {
                group1 ^= num; // numbers with that bit set
            } else {
                group2 ^= num; // numbers without that bit set
            }
        }

        return new int[]{group1, group2};
    }

    public static void main(String[] args) {
        int[] arr1 = {2, 4, 7, 9, 2, 4};
        int[] res1 = findTwoNonRepeating(arr1);
        System.out.println(res1[0] + ", " + res1[1]); // 7, 9

        int[] arr2 = {1, 3, 5, 1, 5, 7};
        int[] res2 = findTwoNonRepeating(arr2);
        System.out.println(res2[0] + ", " + res2[1]); // 3, 7
    }
}

Complexity Analysis

• Time Complexity: O(N) — Two passes through the array
• Space Complexity: O(1) — Only using a few variables

Key Takeaways

1. XOR Properties: a ^ a = 0, a ^ 0 = a — pairs cancel out
2. n & (-n): Isolates the rightmost set bit — powerful trick
3. Splitting by Bit: Numbers that are the same will always go to the same group (their bits are identical)
4. Extension of Single Non-Repeating: The single unique element problem uses just one XOR pass; this extends it cleverly