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