Swap Integers – Equal Sum Matrices

Determine if swapping corresponding elements between two matrices can equalize their sums

Understand the Problem

Problem Statement

Given two integer matrices M1 and M2 of equal size RxC, determine if it's possible to equalize the sum of integers in both matrices by swapping an integer at the same position between the two matrices.

If such a swap is possible, print the two integers that were swapped. If multiple swaps are possible, choose the first occurring swap (in row-major order). If the matrices are already equal in sum or no swap can equalize them, print -1.

Constraints

1 ≤ R, C ≤ 100
-1000 ≤ Matrix elements ≤ 1000
Matrices have equal dimensions
Consider positions in row-major order (top-left to bottom-right)

Examples

Example 1

Input

Output

1 3

Explanation

Swapping the element at position (0,0): M1[0][0]=3 with M2[0][0]=1. After swapping, both matrices have sum=13. The output shows the swapped values: 1 (now in M1) and 3 (now in M2).

Example 2

Input

3 4
18 45 49 11
48 56 31 12
63 21 18 36
35 14 95 10
70 16 36 11
73 30 70 12

Output

-1

Explanation

No single swap at any position can equalize the sums of the two matrices. Therefore the output is -1.

Solution

#include <stdio.h>

int main() {
    int r, c;
    scanf("%d %d", &r, &c);
    
    int m1[100][100], m2[100][100];
    
    // Read first matrix
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%d", &m1[i][j]);
        }
    }
    
    // Read second matrix
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%d", &m2[i][j]);
        }
    }
    
    // Calculate initial sums
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            sum1 += m1[i][j];
            sum2 += m2[i][j];
        }
    }
    
    // Try each position for swapping
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            // Skip if elements are the same
            if (m1[i][j] == m2[i][j]) {
                continue;
            }
            
            // Temporarily swap
            int temp = m1[i][j];
            m1[i][j] = m2[i][j];
            m2[i][j] = temp;
            
            // Calculate new sums
            int newSum1 = sum1 - m2[i][j] + m1[i][j];
            int newSum2 = sum2 - m1[i][j] + m2[i][j];
            
            // Check if sums are equal
            if (newSum1 == newSum2) {
                printf("%d %d\n", m1[i][j], m2[i][j]);
                return 0;
            }
            
            // Restore original values
            m1[i][j] = m2[i][j];
            m2[i][j] = temp;
        }
    }
    
    printf("-1\n");
    return 0;
}

Time:O(R×C) where R and C are matrix dimensions

Space:O(R×C) for storing the matrices

Approach:

The C solution follows the same approach:

Read matrix dimensions and elements using scanf
Calculate initial sums of both matrices
Iterate through each position in row-major order
For each position, if elements differ, temporarily swap them
Calculate new sums efficiently using the formula: newSum = oldSum - oldElement + newElement
If sums become equal, print the swapped values and exit
If no valid swap is found, print -1

The solution uses temporary variables to swap elements and restores them if the swap doesn't work.

Visual Explanation

Loading diagram...

All Problems