☕ DSA Java Articles

Topics › Arrays › Easy

Find the number that appears once, and other numbers twice.

Medium TUF ID 2793 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a non-empty integer array nums in which every element appears exactly twice, except for one element that appears exactly once. Return that single element. The order of the array is arbitrary; the two copies of a value are not necessarily adjacent.

Constraints: 1 ≤ n ≤ 3 × 10^4, n is odd, values fit in a 32-bit signed integer and may be negative or zero. Exactly one element appears once.

Example 1

nums = [4, 1, 2, 1, 2]
answer = 4          // 1 and 2 each appear twice, 4 appears once

Example 2

nums = [2, 2, 1]
answer = 1

Example 3

nums = [7, 0, 7]
answer = 0          // the answer itself can be 0

Approach 1: Brute force

Intuition. The statement is about counts, so count. For each element, scan the whole array and count how many times its value occurs. The first element whose count is 1 is the answer. There is nothing clever here, but it is a correct baseline against which the faster versions can be tested.

Algorithm.

  1. For every index i:
  2. Count the indices j with nums[j] == nums[i].
  3. If the count is 1, return nums[i].
  4. Return -1 if nothing is found (cannot happen with valid input).
static int bruteForce(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] == nums[i]) count++;
        }
        if (count == 1) return nums[i];
    }
    return -1;
}

Complexity. Time O(n^2): each of the n elements triggers a full scan. Space O(1).

Approach 2: Better, count with a hash map (or sort)

Intuition. Counting each value once instead of re-scanning is the standard fix for a nested counting loop: a hash map from value to frequency is built in one pass, and a second pass over the map picks out the key with frequency 1.

Algorithm.

  1. Build freq, a map from value to the number of times it occurs.
  2. Iterate the map entries and return the key whose value is 1.
static int better(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        if (e.getValue() == 1) return e.getKey();
    }
    return -1;
}

Complexity. Time O(n) on average: one pass to build the map and one pass over at most n entries. Space O(n): the map holds about n / 2 + 1 keys.

If you would rather not pay for the map, sort first. In a sorted array every pair sits side by side, so pairs occupy positions (0, 1), (2, 3), ... until the single element breaks the pattern: the first even index i with a[i] != a[i + 1] is the answer, and if no pair is broken the single element is the last one.

static int betterSorting(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    for (int i = 0; i + 1 < a.length; i += 2) {
        if (a[i] != a[i + 1]) return a[i];
    }
    return a[a.length - 1];
}

This is O(n log n) time and O(n) for the defensive copy (or O(1) extra if you are allowed to sort in place). Why does comparing a[i] with a[i + 1] at even indices only suffice? Before the single element, every even index begins a pair, so the test passes. The single element lands at some even index s (because the s / 2 pairs before it fill s positions), and a[s + 1] is the first element of the next pair, which differs from it. After that, the pattern is shifted and we never look at it again because we return immediately.

Both variants are fine answers, but they still use extra memory or extra time. The interviewer is waiting for the next one.

Approach 3: Optimal, XOR everything

Intuition. Bitwise XOR has three properties that together solve the problem in one pass with no memory:

XOR all the elements together. Reorder them mentally so that each pair is adjacent: every pair becomes 0, the zeros vanish, and the only thing left is the single element. This works bit by bit: for each bit position, the paired values contribute an even number of ones, so the parity of that bit across the whole array is exactly the bit of the single element.

Algorithm.

  1. Set x = 0.
  2. For every element v, set x = x ^ v.
  3. Return x.
static int optimal(int[] nums) {
    int x = 0;
    for (int v : nums) x ^= v;
    return x;
}

Dry run on nums = [4, 1, 2, 1, 2] (values in binary):

v binary x after
4 100 100
1 001 101
2 010 111
1 001 110
2 010 100 = 4

Complexity. Time O(n): one pass. Space O(1): a single integer.

A note on negative numbers: Java’s int is a two’s-complement value and ^ operates on all 32 bits, including the sign bit, so negatives need no special handling. XORing Integer.MIN_VALUE with two copies of Integer.MAX_VALUE correctly yields Integer.MIN_VALUE, and the test in the Java file checks exactly that.

Edge cases and pitfalls