thesarfo

Reference

Find the Repeating and Missing Numbers

Finding the one duplicated and one missing number from a 1..n array using hashing vs. a sum-and-sum-of-squares equation system.

views 0

Numbers 1..n, one appears twice (a), one is missing (b). [3,1,2,5,3] → [3,4]. (LeetCode 645)

Brute force: for each 1..n, count its occurrences via linear search — O(n²).

Better — hashing: a frequency array of size n+1; whichever value has frequency 2 is the repeat, whichever has frequency 0 is missing. O(n) time, O(n) space.

Optimal — mathematics: let x = repeating, y = missing. Using the sum of 1..n (Sₙ = n(n+1)/2) and the sum of squares (S₂ₙ = n(n+1)(2n+1)/6):

  • S - Sₙ = x - y (actual sum minus expected sum)
  • S₂ - S₂ₙ = x² - y² = (x-y)(x+y)

Divide the second equation by the first to get x + y, then combine with x - y to solve for both:

public static int[] findMissingRepeatingNumbers(int[] arr) {
    long n = arr.length;
    long SN = (n * (n + 1)) / 2;
    long S2N = (n * (n + 1) * (2 * n + 1)) / 6;


    long S = 0, S2 = 0;
    for (int i = 0; i < n; i++) {
        S += arr[i];
        S2 += (long) arr[i] * (long) arr[i];
    }


    long val1 = S - SN;   // x - y
    long val2 = (S2 - S2N) / val1; // x + y


    long x = (val1 + val2) / 2;
    long y = x - val1;


    return new int[] { (int)x, (int)y };
}

Time: O(n). Space: O(1).