2965. Find Missing and Repeated Values

Intuition

We're given a 2D n x n grid filled with values from 1 to n^2. One number is repeated (A) and one number is missing (B).

To find the missing and repeated numbers, we use mathematical formulas for the sum and sum of squares of the first n^2natural numbers.

the sum of the first n natural numbers:

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$

the sum of squares of the first n natural numbers:

$$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$

Comparing the actual and expected sums helps us form equations to solve for A and B.

Let:

• A be the repeating number

• B be the missing number

We know:

• currentSum = expectedSum - B + A

• currentSqSum = expectedSqSum - B² + A²

From which:

• AMinusB = currentSum - expectedSum = A - B

• ASquaredMinusBSquared = currentSqSum - expectedSqSum = A² - B² = (A - B)(A + B)

So:

• APlusB = ASquaredMinusBSquared / AMinusB

• Then solve: A = (APlusB + AMinusB) / 2 B = APlusB - A

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(n^2)$

Code

public int[] findMissingAndRepeatedValues(int[][] grid) {
    long gridSize = grid.length;
    long currentSum = 0;
    long currentSquaredSum = 0;

    // Step 1: Compute current sum and current squared sum from the grid
    for (int row = 0; row < gridSize; ++row) {
        for (int col = 0; col < gridSize; ++col) {
            currentSum += grid[row][col];
            currentSquaredSum += (grid[row][col] * grid[row][col]);
        }
    }

    // Step 2: Calculate expected sum and expected squared sum for numbers from 1 to n^2
    long totalNumbers = gridSize * gridSize;
    long expectedSum = (totalNumbers * (totalNumbers + 1)) / 2;
    long expectedSquaredSum = (totalNumbers * (totalNumbers + 1) * (2 * totalNumbers + 1)) / 6;

    // Step 3: Derive A - B and A + B
    long aMinusB = currentSum - expectedSum;
    long aSquaredMinusBSquared = currentSquaredSum - expectedSquaredSum;
    long aPlusB = aSquaredMinusBSquared / aMinusB;

    // Step 4: Solve equations to get A and B
    int repeated = (int) (aMinusB + aPlusB) / 2;
    int missing = (int) (aPlusB - repeated);

    // Step 5: Return result
    return new int[]{repeated, missing};
}