Skip to content

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};
}

Comments