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
12
Time Complexity: O (n*m)
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Shivam Pradhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
