# Minimum operations required to make each row and column of matrix equals

Given a square matrix of size . Find minimum number of operation are required such that sum of elements on each row and column becomes equals. In one operation, increment any value of cell of matrix by 1. In first line print minimum operation required and in next ‘n’ lines print ‘n’ integers representing the final matrix after operation.
Example:

```Input:
1 2
3 4
Output:
4
4 3
3 4
Explanation
1. Increment value of cell(0, 0) by 3
2. Increment value of cell(0, 1) by 1
Hence total 4 operation are required

Input: 9
1 2 3
4 2 3
3 2 1
Output:
6
2 4 3
4 2 3
3 3 3
```

The approach is simple, let’s assume that maxSum is the maximum sum among all rows and columns. We just need to increment some cells such that the sum of any row or column becomes ‘maxSum’.
Let’s say Xi is the total number of operation needed to make the sum on row ‘i’ equals to maxSum and Yj is the total number of operation needed to make the sum on column ‘j’ equals to maxSum. Since Xi = Yj so we need to work at any one of them according to the condition.

In order to minimise Xi, we need to choose the maximum from rowSumi and colSumj as it will surely lead to minimum operation. After that, increment ‘i’ or ‘j’ according to the condition satisfied after increment.

Below is the implementation of the above approach.

## C++

 `/* C++ Program to Find minimum number of ` `operation required such that sum of ` `elements on each row and column becomes same*/` `#include ` `using` `namespace` `std; ` ` `  `// Function to find minimum operation required ` `// to make sum of each row and column equals ` `int` `findMinOpeartion(``int` `matrix[], ``int` `n) ` `{ ` `    ``// Initialize the sumRow[] and sumCol[] ` `    ``// array to 0 ` `    ``int` `sumRow[n], sumCol[n]; ` `    ``memset``(sumRow, 0, ``sizeof``(sumRow)); ` `    ``memset``(sumCol, 0, ``sizeof``(sumCol)); ` ` `  `    ``// Calculate sumRow[] and sumCol[] array ` `    ``for` `(``int` `i = 0; i < n; ++i) ` `        ``for` `(``int` `j = 0; j < n; ++j) { ` `            ``sumRow[i] += matrix[i][j]; ` `            ``sumCol[j] += matrix[i][j]; ` `        ``} ` ` `  `    ``// Find maximum sum value in either ` `    ``// row or in column ` `    ``int` `maxSum = 0; ` `    ``for` `(``int` `i = 0; i < n; ++i) { ` `        ``maxSum = max(maxSum, sumRow[i]); ` `        ``maxSum = max(maxSum, sumCol[i]); ` `    ``} ` ` `  `    ``int` `count = 0; ` `    ``for` `(``int` `i = 0, j = 0; i < n && j < n;) { ` ` `  `        ``// Find minimum increment required in ` `        ``// either row or column ` `        ``int` `diff = min(maxSum - sumRow[i], ` `                       ``maxSum - sumCol[j]); ` ` `  `        ``// Add difference in corresponding cell, ` `        ``// sumRow[] and sumCol[] array ` `        ``matrix[i][j] += diff; ` `        ``sumRow[i] += diff; ` `        ``sumCol[j] += diff; ` ` `  `        ``// Update the count variable ` `        ``count += diff; ` ` `  `        ``// If ith row satisfied, increment ith ` `        ``// value for next iteration ` `        ``if` `(sumRow[i] == maxSum) ` `            ``++i; ` ` `  `        ``// If jth column satisfied, increment ` `        ``// jth value for next iteration ` `        ``if` `(sumCol[j] == maxSum) ` `            ``++j; ` `    ``} ` `    ``return` `count; ` `} ` ` `  `// Utility function to print matrix ` `void` `printMatrix(``int` `matrix[], ``int` `n) ` `{ ` `    ``for` `(``int` `i = 0; i < n; ++i) { ` `        ``for` `(``int` `j = 0; j < n; ++j) ` `            ``cout << matrix[i][j] << ``" "``; ` `        ``cout << ````" "````; ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `matrix[] = { { 1, 2 }, ` `                        ``{ 3, 4 } }; ` `    ``cout << findMinOpeartion(matrix, 2) << ````" "````; ` `    ``printMatrix(matrix, 2); ` `    ``return` `0; ` `} `

## Java

 `// Java Program to Find minimum  ` `// number of operation required  ` `// such that sum of elements on  ` `// each row and column becomes same ` `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``// Function to find minimum ` `    ``// operation required ` `    ``// to make sum of each row ` `    ``// and column equals ` `    ``static` `int` `findMinOpeartion(``int` `matrix[][], ` `                                         ``int` `n) ` `    ``{ ` `        ``// Initialize the sumRow[] ` `        ``// and sumCol[] array to 0 ` `        ``int``[] sumRow = ``new` `int``[n]; ` `        ``int``[] sumCol = ``new` `int``[n]; ` `         `  `        ``// Calculate sumRow[] and ` `        ``// sumCol[] array ` `        ``for` `(``int` `i = ``0``; i < n; ++i) ` `  `  `            ``for` `(``int` `j = ``0``; j < n; ++j) ` `            ``{ ` `                ``sumRow[i] += matrix[i][j]; ` `                ``sumCol[j] += matrix[i][j]; ` `            ``} ` `     `  `        ``// Find maximum sum value  ` `        ``// in either row or in column ` `        ``int` `maxSum = ``0``; ` `        ``for` `(``int` `i = ``0``; i < n; ++i)  ` `        ``{ ` `            ``maxSum = Math.max(maxSum, sumRow[i]); ` `            ``maxSum = Math.max(maxSum, sumCol[i]); ` `        ``} ` `     `  `        ``int` `count = ``0``; ` `        ``for` `(``int` `i = ``0``, j = ``0``; i < n && j < n;)  ` `        ``{ ` `            ``// Find minimum increment ` `            ``// required in either row ` `            ``// or column ` `            ``int` `diff = Math.min(maxSum - sumRow[i], ` `                        ``maxSum - sumCol[j]); ` `     `  `            ``// Add difference in  ` `            ``// corresponding cell, ` `            ``// sumRow[] and sumCol[] ` `            ``// array ` `            ``matrix[i][j] += diff; ` `            ``sumRow[i] += diff; ` `            ``sumCol[j] += diff; ` `     `  `            ``// Update the count  ` `            ``// variable ` `            ``count += diff; ` `     `  `            ``// If ith row satisfied, ` `            ``// increment ith value  ` `            ``// for next iteration ` `            ``if` `(sumRow[i] == maxSum) ` `                ``++i; ` `     `  `            ``// If jth column satisfied,  ` `            ``// increment jth value for ` `            ``// next iteration ` `            ``if` `(sumCol[j] == maxSum) ` `                ``++j; ` `        ``} ` `        ``return` `count; ` `    ``} ` ` `  `    ``// Utility function to  ` `    ``// print matrix ` `    ``static` `void` `printMatrix(``int` `matrix[][], ` `                                     ``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < n; ++i)  ` `        ``{ ` `            ``for` `(``int` `j = ``0``; j < n; ++j) ` `                ``System.out.print(matrix[i][j] + ` `                                           ``" "``); ` `          `  `            ``System.out.println(); ` `        ``} ` `    ``} ` ` `  `    ``/* Driver program */` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `matrix[][] = {{``1``, ``2``}, ` `                          ``{``3``, ``4``}}; ` `         `  `        ``System.out.println(findMinOpeartion(matrix, ``2``)); ` `        ``printMatrix(matrix, ``2``); ` ` `  `    ``} ` `} ` ` `  `// This code is contributed by Gitanjali.  `

## Python 3

 `# Python 3 Program to Find minimum  ` `# number of operation required such  ` `# that sum of elements on each row ` `# and column becomes same  ` ` `  `# Function to find minimum operation  ` `# required to make sum of each row  ` `# and column equals ` `def` `findMinOpeartion(matrix, n): ` ` `  `    ``# Initialize the sumRow[] and sumCol[] ` `    ``# array to 0 ` `    ``sumRow ``=` `[``0``] ``*` `n ` `    ``sumCol ``=` `[``0``] ``*` `n ` ` `  `    ``# Calculate sumRow[] and sumCol[] array ` `    ``for` `i ``in` `range``(n): ` `        ``for` `j ``in` `range``(n) : ` `            ``sumRow[i] ``+``=` `matrix[i][j] ` `            ``sumCol[j] ``+``=` `matrix[i][j] ` ` `  `    ``# Find maximum sum value in  ` `    ``# either row or in column ` `    ``maxSum ``=` `0` `    ``for` `i ``in` `range``(n) : ` `        ``maxSum ``=` `max``(maxSum, sumRow[i]) ` `        ``maxSum ``=` `max``(maxSum, sumCol[i]) ` ` `  `    ``count ``=` `0` `    ``i ``=` `0` `    ``j ``=` `0` `    ``while` `i < n ``and` `j < n : ` ` `  `        ``# Find minimum increment required  ` `        ``# in either row or column ` `        ``diff ``=` `min``(maxSum ``-` `sumRow[i],  ` `                   ``maxSum ``-` `sumCol[j]) ` ` `  `        ``# Add difference in corresponding  ` `        ``# cell, sumRow[] and sumCol[] array ` `        ``matrix[i][j] ``+``=` `diff ` `        ``sumRow[i] ``+``=` `diff ` `        ``sumCol[j] ``+``=` `diff ` ` `  `        ``# Update the count variable ` `        ``count ``+``=` `diff ` ` `  `        ``# If ith row satisfied, increment  ` `        ``# ith value for next iteration ` `        ``if` `(sumRow[i] ``=``=` `maxSum): ` `            ``i ``+``=` `1` ` `  `        ``# If jth column satisfied, increment ` `        ``# jth value for next iteration ` `        ``if` `(sumCol[j] ``=``=` `maxSum): ` `            ``j ``+``=` `1` `             `  `    ``return` `count ` ` `  `# Utility function to print matrix ` `def` `printMatrix(matrix, n): ` `    ``for` `i ``in` `range``(n) : ` `        ``for` `j ``in` `range``(n): ` `            ``print``(matrix[i][j], end ``=` `" "``) ` `        ``print``() ` ` `  `# Driver code ` `if` `__name__ ``=``=` `"__main__"``: ` `    ``matrix ``=` `[[ ``1``, ``2` `], ` `              ``[ ``3``, ``4` `]] ` `    ``print``(findMinOpeartion(matrix, ``2``)) ` `    ``printMatrix(matrix, ``2``) ` ` `  `# This code is contributed ` `# by ChitraNayal `

## C#

 `// C# Program to Find minimum  ` `// number of operation required  ` `// such that sum of elements on  ` `// each row and column becomes same ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Function to find minimum ` `    ``// operation required ` `    ``// to make sum of each row ` `    ``// and column equals ` `    ``static` `int` `findMinOpeartion(``int` `[,]matrix, ` `                                        ``int` `n) ` `    ``{ ` `        ``// Initialize the sumRow[] ` `        ``// and sumCol[] array to 0 ` `        ``int``[] sumRow = ``new` `int``[n]; ` `        ``int``[] sumCol = ``new` `int``[n]; ` `         `  `        ``// Calculate sumRow[] and ` `        ``// sumCol[] array ` `        ``for` `(``int` `i = 0; i < n; ++i) ` ` `  `            ``for` `(``int` `j = 0; j < n; ++j) ` `            ``{ ` `                ``sumRow[i] += matrix[i,j]; ` `                ``sumCol[j] += matrix[i,j]; ` `            ``} ` `     `  `        ``// Find maximum sum value  ` `        ``// in either row or in column ` `        ``int` `maxSum = 0; ` `        ``for` `(``int` `i = 0; i < n; ++i)  ` `        ``{ ` `            ``maxSum = Math.Max(maxSum, sumRow[i]); ` `            ``maxSum = Math.Max(maxSum, sumCol[i]); ` `        ``} ` `     `  `        ``int` `count = 0; ` `        ``for` `(``int` `i = 0, j = 0; i < n && j < n;)  ` `        ``{ ` `            ``// Find minimum increment ` `            ``// required in either row ` `            ``// or column ` `            ``int` `diff = Math.Min(maxSum - sumRow[i], ` `                        ``maxSum - sumCol[j]); ` `     `  `            ``// Add difference in  ` `            ``// corresponding cell, ` `            ``// sumRow[] and sumCol[] ` `            ``// array ` `            ``matrix[i,j] += diff; ` `            ``sumRow[i] += diff; ` `            ``sumCol[j] += diff; ` `     `  `            ``// Update the count  ` `            ``// variable ` `            ``count += diff; ` `     `  `            ``// If ith row satisfied, ` `            ``// increment ith value  ` `            ``// for next iteration ` `            ``if` `(sumRow[i] == maxSum) ` `                ``++i; ` `     `  `            ``// If jth column satisfied,  ` `            ``// increment jth value for ` `            ``// next iteration ` `            ``if` `(sumCol[j] == maxSum) ` `                ``++j; ` `        ``} ` `        ``return` `count; ` `    ``} ` ` `  `    ``// Utility function to  ` `    ``// print matrix ` `    ``static` `void` `printMatrix(``int` `[,]matrix, ` `                                    ``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = 0; i < n; ++i)  ` `        ``{ ` `            ``for` `(``int` `j = 0; j < n; ++j) ` `                ``Console.Write(matrix[i,j] + ` `                                        ``" "``); ` `         `  `            ``Console.WriteLine(); ` `        ``} ` `    ``} ` ` `  `    ``/* Driver program */` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[,]matrix = {{1, 2}, ` `                        ``{3, 4}}; ` `         `  `        ``Console.WriteLine(findMinOpeartion(matrix, 2)); ` `        ``printMatrix(matrix, 2); ` ` `  `    ``} ` `} ` ` `  `// This code is contributed by Vt_m.  `

```Output
4
4 3
3 4
```

Time complexity: O(n2)
Auxiliary space: O(n)

Matrix Matrix