Java Programs›Arrays›Find Unique Element

Find Unique Element in Java

intermediate· Arrays · Array

Problem

In an array where every value appears exactly twice except one, that one value is the unique element — the only one without a matching pair.

Given an array where every element appears exactly twice except for one, find that one unique element.

Input

[7, 3, 5, 3, 7]

Output

Unique element: 5

Java Program

Java

public class FindUniqueElement {
    public static void main(String[] args) {
        int[] arr = {7, 3, 5, 3, 7};
        int result = 0;

        // Every value that appears twice cancels itself out via XOR
        for (int num : arr) {
            result ^= num;
        }

        System.out.println("Unique element: " + result);
    }
}

▶ Run Code

Output

Unique element: 5

Core Logic

XOR-ing every element together cancels out every value that appears twice, leaving only the one that appears alone.

How It Works

1result starts at 0, the identity value for XOR — XOR-ing anything with 0 leaves it unchanged.
2Each element in arr is XOR-ed into result in turn.
3x ^ x always evaluates to 0 for any value x, so every element that appears twice cancels itself out somewhere in the sequence.
4Only the element with no matching pair survives all the cancellations, ending up as the final value of result.

For [7, 3, 5, 3, 7], the two 7s cancel each other out, the two 3s cancel each other out, and only 5 is left in result.

💡

Key Point: XOR is both commutative and associative, so the order the elements are XOR-ed in doesn't matter — every matching pair cancels regardless of where it sits in the array.

Complexity

Time Complexity: O(n)Space Complexity: O(1)

Why: A single pass XORs every element into one running result, with no extra data structure needed at all.

Key Concepts

bitwise XORXOR self-cancellation

Approach 2: HashMap Frequency

Java

import java.util.HashMap;
import java.util.Map;

public class FindUniqueElementMap {
    public static void main(String[] args) {
        int[] arr = {7, 3, 5, 3, 7};
        Map<Integer, Integer> freq = new HashMap<>();

        for (int num : arr) {
            // getOrDefault(num, 0) reads the current count, or 0 if unseen, then increments it
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getValue() == 1) { // appeared exactly once
                System.out.println("Unique element: " + entry.getKey());
                break;
            }
        }
    }
}

▶ Run Code

Output

Unique element: 5

Core Logic

Counting every element's frequency and reporting the one with a count of exactly one works even without the 'everyone else appears exactly twice' guarantee the XOR trick relies on.

How It Works

1A HashMap<Integer, Integer> named freq tracks each element's count, built the same way as any other frequency map.
2freq.getOrDefault(num, 0) reads the current count, or 0 if unseen, then freq.put(num, ...) stores the incremented count.
3A second loop walks entrySet(), looking for the one entry whose count equals 1.
4That entry's key is the unique element, printed as soon as it's found.

For [7, 3, 5, 3, 7], the frequency map ends up as 7: 2, 3: 2, 5: 1, so the entry with count 1 — 5 — is reported.

💡

Key Point: This is more general than the XOR trick — it still works if elements appear three or more times, as long as exactly one element has a count different from the rest.

Complexity

Time Complexity: O(n)Space Complexity: O(n)

Why: Building the frequency map visits every element once and holds one entry per distinct value, up to n in the worst case.

Key Concepts

HashMapgetOrDefault()entrySet()

← Previous

Find Union of Arrays

Insertion Sort

Related Programs

Arraysbeginner

Average Array Elements

Check Array Is Sorted

Arraysbeginner

Compare Two Arrays