> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/easy/2965.-find-missing-and-repeated-values.md).

# 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^2`natural 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

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