Interview Question: Find the Single Occurring Number in an Array – Three Solutions

A classic interview question asks for the element that appears only once in an integer array while every other element appears exactly twice.

Example: input [1, 3, 17, 3, 1] yields output 17.

Solution 1: Double Loop

For each element, the algorithm scans the entire array to see if another identical element exists; if none is found, that element is the unique one.

public static int bruteForce(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        boolean found = false;
        for (int j = 0; j < nums.length; j++) {
            // 找到相同值且不是同一个位置的元素
            if (nums[j] == nums[i] && i != j) {
                found = true;
                break;
            }
        }
        if (!found) {
            return nums[i];
        }
    }
    throw new IllegalArgumentException("没有找到唯一数");
}

Time complexity is O(n²) and space complexity O(1). The runtime grows sharply when the data size exceeds tens of thousands.

Solution 2: HashMap – Space for Time

The algorithm records the occurrence count of each number in a HashMap and then returns the key whose count equals 1.

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

public static int hashMap(int[] nums) {
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int num : nums) {
        countMap.put(num, countMap.getOrDefault(num, 0) + 1);
    }
    for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }
    throw new IllegalArgumentException("没有找到唯一数");
}

Time complexity is O(n) with a single pass; space complexity is O(n) because roughly n/2 distinct key‑value pairs are stored.

The approach trades memory for speed, a common optimization strategy.

Java’s autoboxing converts each primitive int to an Integer object, incurring noticeable overhead for large data sets.

A more concise version using the Stream API:

public static int hashMapStream(int[] nums) {
    return Arrays.stream(nums)
            .boxed()
            .collect(Collectors.groupingBy(n -> n, Collectors.counting()))
            .entrySet().stream()
            .filter(e -> e.getValue() == 1)
            .mapToInt(Map.Entry::getKey)
            .findFirst()
            .orElseThrow();
}

Although the Stream version is shorter, the boxing, lambda calls, and intermediate collections add overhead, so its performance is usually inferior to the classic loop.

Solution 3: Bitwise XOR Trick

The XOR operator ( ^) has three key properties:

Any number XORed with itself yields 0: a ^ a = 0.

Any number XORed with 0 yields the number itself: a ^ 0 = a.

XOR is commutative and associative: a ^ b ^ a = b.

Combining these properties, all paired numbers cancel out to 0, leaving the unique number.

Verification with the example:

1 ^ 3 ^ 17 ^ 3 ^ 1
= (1 ^ 1) ^ (3 ^ 3) ^ 17
= 0 ^ 0 ^ 17
= 17

Java implementation requires only three lines of effective code:

public static int xor(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

Time complexity is O(n) and space complexity O(1); only a single int variable is used, with no extra data structures.

A Stream version operates directly on primitive ints, avoiding boxing:

public static int xorStream(int[] nums) {
    return Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);
}

Conclusion

The bitwise XOR solution is the fastest for this specific problem for three reasons:

No boxing overhead—operations are on primitive int values, whereas HashMap requires creating Integer objects, increasing GC pressure at large scales.

No hash‑computation overhead—HashMap incurs cost for computing hash codes, handling collisions, and traversing internal structures.

No memory allocation—HashMap maintains internal arrays and entry nodes, potentially triggering multiple resizings; the XOR method uses only one integer variable.

However, the XOR trick only works when the input satisfies the strict condition that every number appears exactly twice except one. If the condition changes (e.g., two numbers appear once), the XOR result becomes the XOR of the two unique numbers, which cannot be separated directly. The HashMap approach is more general and handles arbitrary frequency patterns.

In most practical scenarios, the HashMap solution is preferred for its versatility despite the higher memory usage.