Tutorialspoint.dev

Find number of transformation to make two Matrix Equal

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:
i) Select any one matrix out of two matrices.
ii) Choose either row/column of selected matrix.
iii) 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
Explaination :
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
Explaination : 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);



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

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.

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.
?>

Output:

12

Time Complexity : O (n*m)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter