☕ DSA Java Articles

Topics › Bit Manipulation › Interview Problems

Single Number - I

Medium TUF ID 143 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a non-empty array of integers nums in which every value appears exactly twice, except for one value that appears exactly once. Return that single value. The interviewer’s follow-up is always the same: do it in linear time and constant extra space, which rules out sorting and hash maps.

Constraints: 1 ≤ n ≤ 3 × 10^4, n is odd, every value fits in a 32-bit signed integer (negatives and zero are allowed). Exactly one value occurs once; every other value occurs exactly twice.

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]
answer = 7            // a lone element is trivially the single one

Approach 1: Brute force

Intuition. The statement is about counts, so count. For each element, scan the whole array and tally how many times its value occurs; the element whose tally is 1 is the answer. There is no cleverness here, only a direct translation of the definition, and that is exactly what makes it slow: every element triggers a full pass.

Algorithm.

  1. For each index i from 0 to n - 1:
  2. Count how many indices j have nums[j] == nums[i].
  3. If that count is 1, return nums[i].
  4. Return -1 if nothing was found (cannot happen for 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 outer iterations performs an n-step inner scan. Space O(1): a couple of counters.

For n = 3 × 10^4 this is about 9 × 10^8 comparisons, which is already at the edge of what passes. Any larger input and it fails.

Approach 2: Better, counting with a hash map (or sorting)

Intuition. The brute force recounts the same values over and over. Count each value once by storing frequencies in a hash map, then look for the entry whose count is 1. This is the standard “frequency table” idea and it is worth knowing because it also solves every variant of this problem (elements appearing three times, two singles, and so on), just not in constant space.

Algorithm.

  1. Build a map freq from value to how many times it occurs, in one pass.
  2. Walk the map’s entries and return the key whose count 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): one pass to build the map and at most n entries to scan, each operation O(1) on average. Space O(n): the map holds roughly n / 2 distinct values.

A sorting variant trades the map for O(n log n) time and no auxiliary hash structure. After sorting, equal values sit side by side, so the array looks like a a b b c d d .... Walk it in steps of two: as long as a[i] == a[i + 1] the pair is intact; the first even index whose partner differs (or which has no partner because it is the last element) is the single value. Note that it copies the array first so the caller’s input is not reordered.

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

Why can the loop safely step by two? Every value before the single element appears exactly twice, so the pairs occupy positions (0, 1), (2, 3), ... and the single element is forced onto an even index. The check i == n - 1 handles the case where the single element is the largest value and therefore sits alone at the end.

Both variants work, but neither meets the “constant extra space” requirement: the map costs O(n), and sorting in place either destroys the input or needs a copy.

Approach 3: Optimal, XOR everything

Intuition. XOR has three properties that together solve this problem outright:

Take the XOR of the whole array. Because order does not matter, mentally regroup the operands so each pair of equal values sits together. Every pair collapses to 0, all those zeros collapse to 0, and the only operand left standing is the single value. No counting, no extra memory, one pass.

Algorithm.

  1. Start with xor = 0.
  2. For each x in nums, set xor ^= x.
  3. Return xor.
static int optimal(int[] nums) {
    int xor = 0;
    for (int x : nums) xor ^= x;
    return xor;
}

Dry run on nums = [4, 1, 2, 1, 2] (three low bits shown):

x binary xor before xor after
4 100 000 100
1 001 100 101
2 010 101 111
1 001 111 110
2 010 110 100

The final value is 100, which is 4. Notice that the second 1 undoes the first 1 and the second 2 undoes the first 2, regardless of the order in which they appeared.

Complexity. Time O(n): one pass with a single XOR per element. Space O(1): a single accumulator.

Why this is genuinely better than the hash map: besides the memory, XOR is a single CPU instruction with no hashing, no boxing of Integers and no cache-unfriendly table. On large inputs it is typically an order of magnitude faster.

Edge cases and pitfalls