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.
leave a comment
0 Comments