Find number of transformation to make two Matrix Equal

Last Updated : 12 Sep, 2023

Given two matrices A and B of order n*m. The task is to find the required number of transformation steps so that both matrices became equal, print -1 if it is not possible.

Transformation step is as:

Select any one matrix out of two matrices.
Choose either row/column of the selected matrix.
Increment every element of select row/column by 1.

Examples :

Input : 
A[2][2]: 1 1
         1 1
B[2][2]: 1 2
         3 4
Output : 3
Explanation :
1 1   ->   1 2   ->   1 2   ->   1 2
1 1   ->   1 2   ->   2 3   ->   3 4

Input :
A[2][2]: 1 1
         1 0
B[2][2]: 1 2
         3 4
Output : -1
Explanation : No transformation will make A and B equal.

The key steps behind the solution of this problem are:

Incrementing any row of A[][] is same as decrementing the same row of B[][]. So, we can have the solution after having the transformation on only one matrix either incrementing or decrementing.

So make A[i][j] = A[i][j] - B[i][j].
For example,
If given matrices are,
A[2][2] : 1 1  
          1 1
B[2][2] : 1 2
          3 4
After subtraction, A[][] becomes,
A[2][2] : 0 -1
         -2 -3

For every transformation either 1st row/ 1st column element necessarily got changed, same is true for other i-th row/column.
If ( A[i][j] – A[i][0] – A[0][j] + A[0][0] != 0) then no solution exists.
Elements of 1st row and 1st column only leads to result.

// Update matrix A[][]
// so that only A[][]
// has to be transformed
for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
        A[i][j] -= B[i][j];

// Check necessary condition
// For condition for 
// existence of full transformation
for (i = 1; i < n; i++)
    for (j = 1; j < m; j++)
        if (A[i][j] - A[i][0] - A[0][j] + A[0][0] != 0)
            return -1;

// If transformation is possible
// calculate total transformation
result = 0;
for (i = 0; i < n; i++)
    result += abs(A[i][0])
for (j = 0; j < m; j++)
    result += abs(A[0][j] - A[0][0]);
return abs(result);

Implementation:

C++

// C++ program to find 
// number of countOpsation 
// to make two matrix equals 
#include <bits/stdc++.h> 
using namespace std; 
  
const int MAX = 1000; 
  
int countOps(int A[][MAX], int B[][MAX],  
             int m, int n) 
{ 
    // Update matrix A[][] 
    // so that only A[][] 
    // has to be countOpsed 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            A[i][j] -= B[i][j]; 
  
    // Check necessary condition 
    // for condition for 
    // existence of full countOpsation 
    for (int i = 1; i < n; i++) 
    for (int j = 1; j < m; j++) 
        if (A[i][j] - A[i][0] -  
            A[0][j] + A[0][0] != 0) 
        return -1; 
  
    // If countOpsation is possible 
    // calculate total countOpsation 
    int result = 0; 
    for (int i = 0; i < n; i++) 
        result += abs(A[i][0]); 
    for (int j = 0; j < m; j++) 
        result += abs(A[0][j] - A[0][0]); 
    return (result); 
} 
  
// Driver code 
int main() 
{ 
    int A[MAX][MAX] = { {1, 1, 1}, 
                        {1, 1, 1}, 
                        {1, 1, 1}}; 
    int B[MAX][MAX] = { {1, 2, 3}, 
                        {4, 5, 6}, 
                        {7, 8, 9}}; 
    cout << countOps(A, B, 3, 3) ; 
    return 0; 
} 

C

// C program to find 
// number of countOpsation 
// to make two matrix equals 
#include <stdio.h> 
  
#define MAX 1000 
  
int abs(int a) 
{ 
  int abs = a; 
  if(abs < 0) 
    abs = abs * (-1); 
  return abs; 
} 
  
int countOps(int A[][MAX], int B[][MAX],  
             int m, int n) 
{ 
    // Update matrix A[][] 
    // so that only A[][] 
    // has to be countOpsed 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            A[i][j] -= B[i][j]; 
  
    // Check necessary condition 
    // for condition for 
    // existence of full countOpsation 
    for (int i = 1; i < n; i++) 
    for (int j = 1; j < m; j++) 
        if (A[i][j] - A[i][0] -  
            A[0][j] + A[0][0] != 0) 
        return -1; 
  
    // If countOpsation is possible 
    // calculate total countOpsation 
    int result = 0; 
    for (int i = 0; i < n; i++) 
        result += abs(A[i][0]); 
    for (int j = 0; j < m; j++) 
        result += abs(A[0][j] - A[0][0]); 
    return (result); 
} 
  
// Driver code 
int main() 
{ 
    int A[MAX][MAX] = { {1, 1, 1}, 
                        {1, 1, 1}, 
                        {1, 1, 1}}; 
    int B[MAX][MAX] = { {1, 2, 3}, 
                        {4, 5, 6}, 
                        {7, 8, 9}}; 
    printf("%d",countOps(A, B, 3, 3)); 
    return 0; 
} 
  
// This code is contributed by kothavvsaakash. 

Java

// Java program to find number of 
// countOpsation to make two matrix 
// equals 
import java.io.*; 
  
class GFG  
{ 
      
    static int countOps(int A[][], int B[][], 
                        int m, int n) 
    { 
          
        // Update matrix A[][] so that only 
        // A[][] has to be countOpsed 
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++) 
                A[i][j] -= B[i][j]; 
      
        // Check necessary condition for  
        // condition for existence of full 
        // countOpsation 
        for (int i = 1; i < n; i++) 
            for (int j = 1; j < m; j++) 
                if (A[i][j] - A[i][0] -  
                    A[0][j] + A[0][0] != 0) 
                    return -1; 
      
        // If countOpsation is possible 
        // calculate total countOpsation 
        int result = 0; 
          
        for (int i = 0; i < n; i++) 
            result += Math.abs(A[i][0]); 
              
        for (int j = 0; j < m; j++) 
            result += Math.abs(A[0][j] - A[0][0]); 
              
        return (result); 
    } 
      
    // Driver code 
    public static void main (String[] args) 
    { 
        int A[][] = { {1, 1, 1}, 
                      {1, 1, 1}, 
                      {1, 1, 1} }; 
                      
        int B[][] = { {1, 2, 3}, 
                      {4, 5, 6}, 
                      {7, 8, 9} }; 
                      
        System.out.println(countOps(A, B, 3, 3)) ; 
  
    } 
} 
  
// This code is contributed by KRV. 

Python3

# Python3 program to find number of 
# countOpsation to make two matrix 
# equals 
def countOps(A, B, m, n): 
  
    # Update matrix A[][] so that only 
    # A[][] has to be countOpsed 
    for i in range(n): 
        for j in range(m): 
            A[i][j] -= B[i][j]; 
  
    # Check necessary condition for  
    # condition for existence of full 
    # countOpsation 
    for i in range(1, n): 
        for j in range(1, n): 
            if (A[i][j] - A[i][0] -
                A[0][j] + A[0][0] != 0): 
                return -1; 
  
    # If countOpsation is possible 
    # calculate total countOpsation 
    result = 0; 
  
    for i in range(n): 
        result += abs(A[i][0]); 
  
    for j in range(m): 
        result += abs(A[0][j] - A[0][0]); 
  
    return (result); 
  
# Driver code 
if __name__ == '__main__': 
    A = [[1, 1, 1], 
         [1, 1, 1], 
         [1, 1, 1]]; 
  
    B = [[1, 2, 3], 
         [4, 5, 6], 
         [7, 8, 9]]; 
           
    print(countOps(A, B, 3, 3)); 
  
# This code is contributed by Rajput-Ji 

C#

// C# program to find number of 
// countOpsation to make two matrix 
// equals 
using System; 
  
class GFG  
{ 
      
    static int countOps(int [,]A, int [,]B, 
                        int m, int n) 
    { 
          
        // Update matrix A[][] so that only 
        // A[][] has to be countOpsed 
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++) 
                A[i, j] -= B[i, j]; 
      
        // Check necessary condition for  
        // condition for existence of full 
        // countOpsation 
        for (int i = 1; i < n; i++) 
            for (int j = 1; j < m; j++) 
                if (A[i, j] - A[i, 0] -  
                    A[0, j] + A[0, 0] != 0) 
                    return -1; 
      
        // If countOpsation is possible 
        // calculate total countOpsation 
        int result = 0; 
          
        for (int i = 0; i < n; i++) 
            result += Math.Abs(A[i, 0]); 
              
        for (int j = 0; j < m; j++) 
            result += Math.Abs(A[0, j] - A[0, 0]); 
              
        return (result); 
    } 
      
    // Driver code 
    public static void Main () 
    { 
        int [,]A = { {1, 1, 1}, 
                     {1, 1, 1}, 
                     {1, 1, 1} }; 
                          
        int [,]B = { {1, 2, 3}, 
                     {4, 5, 6}, 
                     {7, 8, 9} }; 
                          
    Console.Write(countOps(A, B, 3, 3)) ; 
  
    } 
} 
  
// This code is contributed by nitin mittal. 

PHP

<?php 
// PHP program to find 
// number of countOpsation 
// to make two matrix equals 
  
function countOps($A, $B,  
                  $m, $n) 
{ 
    $MAX = 1000; 
      
    // Update matrix A[][] 
    // so that only A[][] 
    // has to be countOpsed 
    for ($i = 0; $i < $n; $i++) 
        for ($j = 0; $j < $m; $j++) 
            $A[$i][$j] -= $B[$i][$j]; 
  
    // Check necessary condition 
    // for condition for 
    // existence of full countOpsation 
    for ($i = 1; $i < $n; $i++) 
    for ($j = 1; $j < $m; $j++) 
        if ($A[$i][$j] - $A[$i][0] -  
            $A[0][$j] + $A[0][0] != 0) 
        return -1; 
  
    // If countOpsation is possible 
    // calculate total countOpsation 
    $result = 0; 
    for ($i = 0; $i < $n; $i++) 
        $result += abs($A[$i][0]); 
    for ($j = 0; $j < $m; $j++) 
        $result += abs($A[0][$j] - $A[0][0]); 
    return ($result); 
} 
  
    // Driver code 
    $A = array(array(1, 1, 1), 
               array(1, 1, 1), 
               array(1, 1, 1)); 
                 
    $B = array(array(1, 2, 3), 
               array(4, 5, 6), 
               array(7, 8, 9)); 
    echo countOps($A, $B, 3, 3) ; 
  
// This code is contributed by nitin mittal. 
?> 

Javascript

<script> 
  
// JavaScript program to find number of 
// countOpsation to make two matrix 
// equals 
function countOps(A, B, m, n) 
{ 
      
    // Update matrix A[][] so that only 
    // A[][] has to be countOpsed 
    for (var i = 0; i < n; i++) 
        for (var j = 0; j < m; j++) 
            A[i][j] -= B[i][j]; 
  
    // Check necessary condition for  
    // condition for existence of full 
    // countOpsation 
    for (var i = 1; i < n; i++) 
        for (var j = 1; j < m; j++) 
            if (A[i][j] - A[i][0] -  
                A[0][j] + A[0][0] != 0) 
                return -1; 
  
    // If countOpsation is possible 
    // calculate total countOpsation 
    var result = 0; 
      
    for (var i = 0; i < n; i++) 
        result += Math.abs(A[i][0]); 
          
    for (var j = 0; j < m; j++) 
        result += Math.abs(A[0][j] - A[0][0]); 
          
    return (result); 
} 
  
// Driver code 
 var A = [ [1, 1, 1], 
              [1, 1, 1], 
              [1, 1, 1] ]; 
                   
 var B = [ [1, 2, 3], 
              [4, 5, 6], 
              [7, 8, 9] ]; 
                   
document.write(countOps(A, B, 3, 3)) ; 
  
  
</script>

Output

Time Complexity: O (n*m)
Auxiliary Space: O(1)

Suggest improvement

Find all permuted rows of a given row in a matrix

Inplace (Fixed space) M x N size matrix transpose

Share your thoughts in the comments

Basic Operations on Matrix

Easy problems on Matrix

Intermediate problems on Matrix

Hard problems on Matrix