☕ DSA Java Articles

Topics › Arrays › Hard

Find the repeating and missing number

Hard TUF ID 21 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array arr of n integers that was meant to contain each value from 1 to n exactly once. One value x appears twice and, as a consequence, one value y is missing. Return {x, y}: the repeating number first, the missing number second.

Constraints: 2 ≤ n ≤ 10^5, 1 ≤ arr[i] ≤ n, exactly one value is duplicated and exactly one is absent.

Example 1

arr = [3, 1, 2, 5, 3]
answer = [3, 4]

3 occurs twice and 4 never occurs.

Example 2

arr = [2, 2]
answer = [2, 1]

The smallest possible input: 2 repeats, 1 is missing.

Approach 1: Brute force

Intuition. For every candidate value v from 1 to n, scan the array and count how many times v appears. A count of 2 marks the repeating number, a count of 0 marks the missing one. Stop once both are known.

Algorithm.

  1. For v = 1 .. n: count occurrences of v in arr.
  2. If the count is 2, repeating = v; if it is 0, missing = v.
  3. Break when both are set; return {repeating, missing}.
static int[] bruteForce(int[] arr) {
    int n = arr.length, repeating = -1, missing = -1;
    for (int v = 1; v <= n; v++) {
        int count = 0;
        for (int x : arr) if (x == v) count++;
        if (count == 2) repeating = v;
        else if (count == 0) missing = v;
        if (repeating != -1 && missing != -1) break;
    }
    return new int[]{repeating, missing};
}

Complexity. Time O(n^2): up to n candidates, each a full scan. Space O(1).

Too slow for n = 10^5 (10^10 comparisons in the worst case).

Approach 2: Better, a frequency array

Intuition. Counting every value in one pass is what a frequency array does. Since the values are confined to 1 .. n, an int[n + 1] indexed by value is a perfect hash: bump freq[x] for each element, then look for the index with count 2 and the index with count 0.

Algorithm.

  1. freq = new int[n + 1]; for each x in arr, freq[x]++.
  2. For v = 1 .. n: freq[v] == 2 gives the repeating value, freq[v] == 0 the missing one.
static int[] better(int[] arr) {
    int n = arr.length;
    int[] freq = new int[n + 1];
    for (int x : arr) freq[x]++;
    int repeating = -1, missing = -1;
    for (int v = 1; v <= n; v++) {
        if (freq[v] == 2) repeating = v;
        else if (freq[v] == 0) missing = v;
    }
    return new int[]{repeating, missing};
}

Complexity. Time O(n): two linear passes. Space O(n) for the frequency array.

This is fast and clear. The remaining challenge, and the reason the problem is marked hard, is doing it in constant extra space.

Approach 3: Optimal, two equations (sum and sum of squares)

Intuition. Compare the array with the ideal sequence 1 .. n. The array’s sum differs from 1 + 2 + ... + n by exactly x - y: it contains an extra x and lacks a y. Likewise the sum of squares differs by x^2 - y^2. That gives two equations in two unknowns:

S  - Sn  = x - y
S2 - S2n = x^2 - y^2 = (x - y)(x + y)

Divide the second by the first to get x + y, then solve: x = ((x - y) + (x + y)) / 2 and y = x - (x - y). Division is exact because x ≠ y, so x - y ≠ 0.

Algorithm.

  1. Sn = n(n+1)/2, S2n = n(n+1)(2n+1)/6.
  2. One pass to compute S (sum) and S2 (sum of squares) of the array, in long.
  3. diff = S - Sn (that is x - y), sumXY = (S2 - S2n) / diff.
  4. x = (diff + sumXY) / 2, y = x - diff.
static int[] optimalMath(int[] arr) {
    long n = arr.length;
    long sn = n * (n + 1) / 2;                       // 1 + 2 + ... + n
    long s2n = n * (n + 1) * (2 * n + 1) / 6;        // 1^2 + 2^2 + ... + n^2
    long s = 0, s2 = 0;
    for (int v : arr) {
        s += v;
        s2 += (long) v * v;
    }
    long diff = s - sn;                              // x - y   (x repeating, y missing)
    long sumXY = (s2 - s2n) / diff;                  // x + y   since x^2 - y^2 = (x - y)(x + y)
    long x = (diff + sumXY) / 2;
    long y = x - diff;
    return new int[]{(int) x, (int) y};
}

Dry run on arr = [3, 1, 2, 5, 3], n = 5: Sn = 15, S2n = 55, S = 14, S2 = 9 + 1 + 4 + 25 + 9 = 48. diff = -1, sumXY = (48 - 55) / (-1) = 7, x = (-1 + 7) / 2 = 3, y = 3 - (-1) = 4. Answer [3, 4].

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

Everything must be computed in long. For n = 10^5, S2n ≈ 3.3 × 10^14 and even n(n+1)(2n+1) is about 2 × 10^15, both far beyond int. The Java tests include n = 100000 precisely to catch an int slip.

Approach 4: Optimal, xor and bit bucketing

Intuition. Xor-ing all array values together with all of 1 .. n cancels every value that appears an even number of times. The correct values appear twice (once in the array, once in 1 .. n), the repeating x appears three times and the missing y once, so the result is x ^ y. That alone does not separate them, but any set bit of x ^ y is a bit where x and y differ. Pick the lowest such bit and split every number (array values and 1 .. n alike) into two buckets by that bit. Within each bucket all values again cancel in pairs except for one of x or y, so xor-ing each bucket yields the two numbers. A final count over the array tells which of the two is the duplicate.

Algorithm.

  1. xr = arr[0] ^ ... ^ arr[n-1] ^ 1 ^ ... ^ n, which equals x ^ y.
  2. bit = xr & -xr, the lowest set bit.
  3. Xor the array values and the numbers 1 .. n into one (bit set) or zero (bit clear).
  4. Count how often one occurs in arr: twice means one is the repeating number, otherwise zero is.
static int[] optimalXor(int[] arr) {
    int n = arr.length, xr = 0;
    for (int i = 0; i < n; i++) xr ^= arr[i] ^ (i + 1);   // every value pairs off except x and y: xr = x ^ y
    int bit = xr & -xr;                                   // lowest bit where x and y differ
    int zero = 0, one = 0;
    for (int i = 0; i < n; i++) {
        if ((arr[i] & bit) != 0) one ^= arr[i]; else zero ^= arr[i];
        if (((i + 1) & bit) != 0) one ^= (i + 1); else zero ^= (i + 1);
    }
    int count = 0;                                        // decide which bucket holds the repeating number
    for (int v : arr) if (v == one) count++;
    return count == 2 ? new int[]{one, zero} : new int[]{zero, one};
}

Complexity. Time O(n): three linear passes. Space O(1). No overflow is possible because xor never leaves the int range.

Which optimal approach should you reach for? The math one is shorter and more common in interviews, but it depends on exact long arithmetic: S2n is about 3.3 × 10^14 for n = 10^5 and 3.3 × 10^17 for n = 10^6, both inside long, yet the intermediate n * (n + 1) * (2n + 1) computed with n as an int already overflows for n just above 1000. The xor one is bulletproof against overflow and generalises to “two numbers appear once, everything else twice”.

Edge cases and pitfalls