Find Missing and Repeated Values

class Solution {
public:
    vector<int> detectRepeatAndMissing(vector<vector<int>>& matrix) {
        long long totalSum = 0, totalSqrSum = 0;
        long long dimension = matrix.size();
        long long perfectTotal = dimension * dimension;

        // Calculate sum and square sum from the matrix
        for (int i = 0; i < dimension; ++i) {
            for (int j = 0; j < dimension; ++j) {
                totalSum += matrix[i][j];
                totalSqrSum +=
                    static_cast<long long>(matrix[i][j]) * matrix[i][j];
            }
        }

        // Expected and actual sum computations
        long long expectedSum = perfectTotal * (perfectTotal + 1) / 2;
        long long expectedSqrSum = perfectTotal * (perfectTotal + 1) * (2 * perfectTotal + 1) / 6;

        // Calculate differences from expected values
        long long diffSum = totalSum - expectedSum;
        long long diffSqrSum = totalSqrSum - expectedSqrSum;

        // Solve the equations for missing and repeated values
        int repeated = (diffSqrSum / diffSum + diffSum) / 2;
        int missing = (diffSqrSum / diffSum - diffSum) / 2;

        return {repeated, missing};
    }
};

In the provided C++ solution, the objective is to identify a missing and a repeated number within a matrix where the numbers range from 1 to the total number of elements (N*N). The approach revolves around leveraging mathematical properties of sums and square sums:

• Sum Calculation:

  • Calculate the sum (totalSum) and square sum (totalSqrSum) of all elements in the matrix.
  • Calculate the theoretically perfect sum (expectedSum) and square sum (expectedSqrSum) for a sequence from 1 to N*N.

• Differences Identification:

  • Derive differences between the calculated sums and expected sums.

• Solution through Equations:

  • Use the differences to set up and solve equations that pinpoint the values of the missing and repeated numbers.

The function returns the repeated and missing numbers in this format: {repeated, missing}. This solution is efficient as it reduces the problem to evaluating simple formulas based on sum and square sum, instead of relying on iterative or mapping-based approaches which might be less space-efficient.

class Solution {

    public int[] detectDuplicateAndMissing(int[][] matrix) {
        long aggregate = 0, aggregateOfSquares = 0;
        long dimension = matrix.length;
        long maxNum = dimension * dimension;

        // Summing up elements and their squares in the matrix
        for (int i = 0; i < dimension; ++i) {
            for (int j = 0; j < dimension; ++j) {
                aggregate += matrix[i][j];
                aggregateOfSquares += (long) matrix[i][j] * matrix[i][j];
            }
        }

        // Difference from the expected total and square sums
        // Expected sum: n(n+1)/2, Expected square sum: n(n+1)(2n+1)/6
        long difference = aggregate - (maxNum * (maxNum + 1)) / 2;
        long squareDifference = aggregateOfSquares - (maxNum * (maxNum + 1) * (2 * maxNum + 1)) / 6;

        // Resolve using equations for repeat (x) and miss (y)
        // difference = x - y
        // squareDifference = x² - y²
        int duplicate = (int) (squareDifference / difference + difference) / 2;
        int missing = (int) (squareDifference / difference - difference) / 2;

        return new int[] { duplicate, missing };
    }
}

This Java solution provides a method to detect duplicated and missing values within a 2D square matrix with dimensions (n \times n). It utilizes mathematical properties to efficiently find the values by calculating sums and square sums of its elements.

• Sum all elements in the matrix and also their squares. This helps establish a base to compare against expected sums if the matrix had all unique values from 1 to n(^2).

• Compute the two expected theoretical sums:

  • The arithmetic sum of the first n(^2) integers.
  • The sum of squares of the first n(^2) integers.

• Calculate the difference between the actual sums (derived from the matrix elements) and the expected sums. This provides two critical pieces of information:

  • The straightforward difference gives the subtraction result between the missing and duplicated number.
  • The squared difference, when manipulated through algebraic identities, helps isolate the missing and duplicated numbers.

• Utilize derived equations from these differences:

  • The equation derived from the direct sum difference gives (x - y), where x is the duplicate number and y is the missing.
  • The equation from the squared sum difference, when expanded (x² - y² = (x + y)(x - y)), provides another approach to identifying x and y.

• Given these two fundamental equations, solve for 'x' and 'y', providing the duplicate and missing numbers from the matrix.

This method is highly efficient due to its reliance on simple arithmetic operations and dives directly into the problem without the need for complex operations or nested loops beyond the initial data gathering.

class Solution:
    def calculateDifferences(self, matrix: List[List[int]]) -> List[int]:
        # Matrix size
        m = len(matrix)
        expected_square = m * m
        
        # Summations from provided matrix
        total_sum = sum(value for row in matrix for value in row)
        total_sqr_sum = sum(value * value for row in matrix for value in row)

        # Differences from the expected values for sum and square sum
        diff_sum = total_sum - expected_square * (expected_square + 1) // 2
        diff_sqr_sum = total_sqr_sum - expected_square * (expected_square + 1) * (2 * expected_square + 1) // 6

        # Calculation of repeated and missing based on the differences
        repeated_val = (diff_sqr_sum // diff_sum + diff_sum) // 2
        missing_val = (diff_sqr_sum // diff_sum - diff_sum) // 2

        return [repeated_val, missing_val]

The Find Missing and Repeated Values solution in Python3 effectively determines the duplicated and missing values from a given matrix. Initially, the solution calculates the matrix's order m * m, representing the expected sum of numbers and squares if no numbers were missing or repeated. Following this, it computes the actual total sum and sum of squares for the elements in the matrix.

The critical step involves determining the discrepancies between the expected and actual sums, as well as the sum of squares. These differences enable the formula to derive both the repeated and missing integers through algebraic manipulation. The final return provides the identified repeated and missing values in the form of a list. This method ensures a systematic approach to solving the problem by leveraging mathematical properties.