Find the repeating and the missing

The problem, simply

You get an array of n numbers. It should hold every number from 1 to n exactly once, in any order. But one number r appears twice, and so one number m is missing.

Return both: the repeating number and the missing number.

A story to remember it

Picture it

Examples

Way 1: the simple way

For every number v from 1 to n, count how many boxes hold it. A count of 2 means v repeats. A count of 0 means v is missing.

class Solution {
    public int[] findTwoElement(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;
            if (count == 0) missing = v;
        }
        return new int[] { repeating, missing };
    }
}

How long it takes: n numbers, each counted over n boxes, O(n^2). Extra room: O(1).

Way 2: the clever way

Use two clues, both easy to compute in one walk:

1. Sum clue. The real sum of 1 to n is n(n+1)/2. The array's sum minus that is r - m, because r came in an extra time and m never did.
2. Square clue. The real sum of squares is n(n+1)(2n+1)/6. The array's squares minus that is r*r - m*m, which equals (r - m)(r + m).
3. Divide the square clue by the sum clue to get r + m.
4. Now r = ((r - m) + (r + m)) / 2, and m = r - (r - m).

class Solution {
    public int[] findTwoElement(int[] arr) {
        long n = arr.length;
        long sum = 0, squares = 0;
        for (int x : arr) {
            sum += x;
            squares += (long) x * x;
        }
        long diff = sum - n * (n + 1) / 2;                          // r - m
        long sqDiff = squares - n * (n + 1) * (2 * n + 1) / 6;      // r*r - m*m
        long both = sqDiff / diff;                                   // r + m
        long r = (diff + both) / 2;
        long m = r - diff;
        return new int[] { (int) r, (int) m };
    }
}

How long it takes: one walk over the array, O(n). Extra room: a few numbers, O(1). The array is not changed.

Another way: mark the boxes

Use the array itself as a checklist. When you see value v, make box v - 1 negative, as a tick. If box v - 1 is already negative, v is the repeat. At the end, the one box that is still positive is the missing number's box.

class Solution {
    public int[] findTwoElement(int[] arr) {
        int repeating = -1, missing = -1;
        for (int i = 0; i < arr.length; i++) {
            int v = Math.abs(arr[i]);
            if (arr[v - 1] < 0) repeating = v;   // already ticked: seen before
            else arr[v - 1] = -arr[v - 1];       // tick box v - 1
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) missing = i + 1;     // never ticked
            arr[i] = Math.abs(arr[i]);           // put the array back
        }
        return new int[] { repeating, missing };
    }
}

This is also O(n) time and O(1) room, and it cannot overflow, but it writes into the input while it works.

Watch out for

• Getting the sign backwards. sum - expected is r - m, which is negative when the repeat is smaller than the missing number. Keep the sign; the formulas handle it.
• The order of the answer. GeeksforGeeks wants [repeating, missing]. Check what your judge expects.
• In the marking way, read Math.abs(arr[i]), because the box you are reading may already have been ticked.

What interviewers ask next

• Can you do it with XOR? XOR all values and all of 1 to n. Pairs cancel, leaving r XOR m. Split every number by one bit where r and m differ, XOR each group, and you get r and m. Check which one appears in the array to tell them apart.
• What if the array is read-only and big? The math way only reads, so it is the answer.
• Only a missing number, nothing repeated? Expected sum minus actual sum. Or XOR, which never overflows.
• Find the duplicate in n + 1 numbers from 1 to n without changing the array (LeetCode 287)? Treat values as arrows to positions and use fast and slow pointers to find the loop.

Remember this

Grown-up words: the two clues are a system of two equations, the sum formulas are arithmetic series, ticking boxes by making them negative is in-place index marking, and the XOR trick uses the lowest set bit to split the numbers.