A beautiful matrix is a matrix in which the sum of elements in each row and column is equal.
Given a square matrix of size NxN. Find the minimum number of operation(s) that are required to make the matrix beautiful. In one operation you can increment the value of any one cell by 1.
Example 1:
Input:
N = 2
matrix[][] = {{1, 2},
              {3, 4}}
Output: 4
Explanation:
Updated matrix:
4 3
3 4
1. Increment value of cell(0, 0) by 3
2. Increment value of cell(0, 1) by 1
Hence total 4 operation are required.
Example 2:
Input:
N = 3
matrix[][] = {{1, 2, 3},
              {4, 2, 3},
              {3, 2, 1}}
Output: 6
Explanation:
Original matrix is as follows:
1 2 3
4 2 3
3 2 1
We need to make increment in such a way 
that each row and column has one time 2, 
one time 3 , one time 4. For that we 
need 6 operations.
Your Task: 
You don't need to read input or print anything. Complete the function findMinOpeartion() that takes matrix and n as input parameters and returns the minimum number of operations.
Expected Time Complexity: O(N * N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 100
1 <= matrix[i][j] <= 200

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: 
#User function Template for python3

class Solution:
    
    #Function to find minimum number of operations that are required 
    #to make the matrix beautiful.
    def findMinOpeartion(self, matrix, n):
        # code here

Solutions:
class Solution:

	def findMinOpeartion(self, matrix, n):
		ts = 0
		hs = 0
		for i in range(n):
			cr = 0
			for j in range(n):
				ts += matrix[i][j]
				cr += matrix[i][j]
			cc = 0
			for j in range(n):
				cc += matrix[j][i]
			hs = max(cc, cr, hs)
		return n * hs - ts


class Solution:

	def findMinOpeartion(self, matrix, n):
		sumRow = [0] * n
		sumCol = [0] * n
		for i in range(n):
			for j in range(n):
				sumRow[i] += matrix[i][j]
				sumCol[j] += matrix[i][j]
		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:
			diff = min(maxSum - sumRow[i], maxSum - sumCol[j])
			matrix[i][j] += diff
			sumRow[i] += diff
			sumCol[j] += diff
			count += diff
			if sumRow[i] == maxSum:
				i += 1
			if sumCol[j] == maxSum:
				j += 1
		return count


class Solution:

	def findMinOpeartion(self, matrix, n):
		ma = max((sum(matrix[i]) for i in range(n)))
		for i in range(n):
			ma = max(ma, sum([matrix[j][i] for j in range(n)]))
		ans = 0
		for i in range(n):
			ans += ma - sum(matrix[i])
		return ans


class Solution:

	def findMinOpeartion(self, matrix, n):
		s = 0
		for i in range(n):
			for j in range(n):
				s += matrix[i][j]
		mx = 0
		for i in range(n):
			(row, col) = (0, 0)
			for j in range(n):
				row += matrix[i][j]
				col += matrix[j][i]
			mx = max(mx, row, col)
		return mx * n - s


class Solution:

	def findMinOpeartion(self, matrix, n):
		ma = 0
		total = 0
		for i in range(n):
			a = 0
			b = 0
			for j in range(n):
				a += matrix[i][j]
				b += matrix[j][i]
			ma = max(ma, a, b)
			total += a
		ma = ma * n
		return ma - total


class Solution:

	def findMinOpeartion(self, matrix, n):
		sum_row = [0] * n
		sum_col = [0] * n
		for i in range(n):
			for j in range(n):
				sum_row[i] += matrix[i][j]
				sum_col[j] += matrix[i][j]
		max_sum = max(sum_row + sum_col)
		(i, j, count) = (0, 0, 0)
		while i < n and j < n:
			diff = min(max_sum - sum_row[i], max_sum - sum_col[j])
			sum_row[i] += diff
			sum_col[j] += diff
			count += diff
			if sum_row[i] == max_sum:
				i += 1
			if sum_col[j] == max_sum:
				j += 1
		return count


class Solution:

	def findMinOpeartion(self, matrix, n):
		sums_r = [sum(row) for row in matrix]
		sums_c = [sum(col) for col in zip(*matrix)]
		max_r = max(sums_r)
		max_c = max(sums_c)
		diff_r = sum((max_r - row for row in sums_r))
		diff_c = sum((max_c - col for col in sums_c))
		return max(diff_r, diff_c)


class Solution:

	def findMinOpeartion(self, matrix, n):

		def row(matrix):
			ans = []
			n = len(matrix)
			for i in range(n):
				x = 0
				for j in range(n):
					x += matrix[i][j]
				ans.append(x)
			return ans

		def column(matrix):
			n = len(matrix)
			ans = []
			for i in range(n):
				current = 0
				for j in range(n):
					current += matrix[j][i]
				ans.append(current)
			return ans
		r = row(matrix)
		c = column(matrix)
		maximum = max(max(r), max(c))
		ans = 0
		for i in r:
			ans += maximum - i
		return ans


class Solution:

	def findMinOpeartion(self, matrix, n):
		r = []
		for i in matrix:
			r.append(sum(i))
		c = []
		for i in range(n):
			x = 0
			for j in range(n):
				x += matrix[j][i]
			c.append(x)
		maximum = max(max(r), max(c))
		ans = 0
		for i in r:
			ans += maximum - i
		return ans


class Solution:

	def findMinOpeartion(self, matrix, n):

		def row(matrix):
			ans = []
			for i in matrix:
				ans.append(sum(i))
			return ans

		def column(matrix):
			n = len(matrix)
			ans = []
			for i in range(n):
				current = 0
				for j in range(n):
					current += matrix[j][i]
				ans.append(current)
			return ans
		r = row(matrix)
		c = column(matrix)
		ans = 0
		a = max(r)
		b = max(c)
		m = max(a, b)
		for i in r:
			ans += m - i
		return ans


import sys

class Solution:

	def findMinOpeartion(self, matrix, n):
		res = -sys.maxsize
		(sumR, sumC) = (0, 0)
		for i in range(n):
			(sumR, sumC) = (0, 0)
			for j in range(n):
				sumR += matrix[i][j]
				sumC += matrix[j][i]
			res = max(res, max(sumR, sumC))
		min = 0
		for i in range(n):
			sum1 = 0
			for j in range(n):
				sum1 += matrix[i][j]
			min += res - sum1
		return min


import math

class Solution:

	def findMinOpeartion(self, matrix, n):
		row_sums = [0] * n
		col_sums = [0] * n
		total_sum = 0
		for i in range(n):
			for j in range(n):
				row_sums[i] += matrix[i][j]
				col_sums[j] += matrix[i][j]
				total_sum += matrix[i][j]
		max_sum = 0
		for i in range(n):
			max_sum = max(max_sum, row_sums[i], col_sums[i])
		return max_sum * n - total_sum


class Solution:

	def findMinOpeartion(self, matrix, n):
		maxsum = 0
		res = 0
		for i in range(n):
			rsum = 0
			csum = 0
			for j in range(n):
				rsum = rsum + matrix[i][j]
				csum = csum + matrix[j][i]
			maxsum = max(maxsum, rsum, csum)
		for i in range(n):
			rsum = 0
			for j in range(n):
				rsum = rsum + matrix[i][j]
			res += maxsum - rsum
		return res


class Solution:

	def findMinOpeartion(self, mat, n):
		(rowsum, colsum) = (0, 0)
		(maxi, sumi) = (0, 0)
		for i in range(n):
			(rowsum, colsum) = (0, 0)
			for j in range(n):
				rowsum += mat[i][j]
				colsum += mat[j][i]
				sumi += mat[i][j]
			maxi = max(maxi, rowsum, colsum)
		return maxi * n - sumi


class Solution:

	def findMinOpeartion(self, matrix, n):
		rowsum = [0] * n
		colsum = [0] * n
		for i in range(n):
			for j in range(n):
				rowsum[i] += matrix[i][j]
				colsum[j] += matrix[i][j]
		maxsum = 0
		for i in range(n):
			maxsum = max(maxsum, rowsum[i])
			maxsum = max(maxsum, colsum[i])
		i = j = count = 0
		while i < n and j < n:
			dif = min(maxsum - rowsum[i], maxsum - colsum[j])
			count += dif
			rowsum[i] += dif
			colsum[j] += dif
			matrix[i][j] += dif
			if rowsum[i] == maxsum:
				i += 1
			if colsum[j] == maxsum:
				j += 1
		return count


class Solution:

	def findMinOpeartion(self, mat, n):
		(row, col) = ([], [])
		for i in range(n):
			row.append(sum(mat[i]))
			cur = 0
			for j in range(n):
				cur += mat[j][i]
			col.append(cur)
		(i, j) = (0, 0)
		ans = 0
		pos = max(max(row), max(col))
		while i < n and j < n:
			cur = min(pos - row[i], pos - col[j])
			ans += cur
			row[i] += cur
			col[j] += cur
			if row[i] == pos:
				i += 1
			if col[j] == pos:
				j += 1
		return ans


class Solution:

	def findMinOpeartion(self, matrix, n):
		rowsums = [sum(x) for x in matrix]
		colsums = [sum([matrix[j][i] for j in range(n)]) for i in range(n)]
		maxsum = max(max(rowsums), max(colsums))
		rowsums = [maxsum - x for x in rowsums]
		colsums = [maxsum - x for x in colsums]
		s = 0
		for i in range(n):
			for j in range(n):
				t = min(rowsums[i], colsums[j])
				s += t
				rowsums[i] -= t
				colsums[j] -= t
		return s


class Solution:

	def findMinOpeartion(self, matrix, n):
		n = len(matrix)
		rowsum = [0] * n
		colsum = [0] * n
		mxsum = 0
		for i in range(n):
			for j in range(n):
				rowsum[i] += matrix[i][j]
				colsum[j] += matrix[i][j]
		for i in range(n):
			mxsum = max(mxsum, rowsum[i])
			mxsum = max(mxsum, colsum[i])
		(i, j) = (0, 0)
		ans = 0
		while i < n and j < n:
			diff = min(mxsum - rowsum[i], mxsum - colsum[j])
			matrix[i][j] += diff
			rowsum[i] += diff
			colsum[j] += diff
			ans += diff
			if rowsum[i] == mxsum:
				i += 1
			if colsum[j] == mxsum:
				j += 1
		return ans


class Solution:

	def findMinOpeartion(self, matrix, n):
		maxa1 = 0
		suma = 0
		for i in range(len(matrix)):
			k = 0
			for j in range(len(matrix[0])):
				k += matrix[i][j]
				suma += matrix[i][j]
			maxa1 = max(maxa1, k)
		maxa2 = 0
		for j in range(len(matrix[0])):
			k = 0
			for i in range(len(matrix)):
				k += matrix[i][j]
			maxa2 = max(maxa2, k)
		return max(maxa1 * len(matrix), maxa2 * len(matrix[0])) - suma


class Solution:

	def findMinOpeartion(self, m, n):
		rows = len(m)
		columns = len(m[0])
		row_sum = [0] * rows
		col_sum = [0] * columns
		max_sum = 0
		for i in range(rows):
			for j in range(columns):
				row_sum[i] += m[i][j]
				if row_sum[i] > max_sum:
					max_sum = row_sum[i]
				col_sum[j] += m[i][j]
				if col_sum[j] > max_sum:
					max_sum = col_sum[j]
		operations = 0
		for i in range(rows):
			if row_sum[i] == max_sum:
				continue
			for j in range(columns):
				if col_sum[j] == max_sum:
					continue
				change = max_sum - max(row_sum[i], col_sum[j])
				operations += change
				m[i][j] += change
				row_sum[i] += change
				col_sum[j] += change
		return operations


class Solution:

	def findMinOpeartion(self, matrix, n):
		(max_sum, row_sum) = self.getMaxSumRowSum(matrix, n)
		result = 0
		for row in row_sum:
			result += max_sum - row
		return result

	def getMaxSumRowSum(self, matrix, n):
		max_sum = 0
		row_sum = [0 for _ in range(n)]
		col_sum = [0 for _ in range(n)]
		for row in range(n):
			for col in range(n):
				row_sum[row] += matrix[row][col]
				col_sum[col] += matrix[row][col]
		return (max(max(row_sum), max(col_sum)), row_sum)


class Solution:

	def findMinOpeartion(self, matrix, n):
		rowSum = [0 for i in range(n)]
		coulmnSum = [0 for i in range(n)]
		for i in range(n):
			for j in range(n):
				rowSum[i] += matrix[i][j]
				coulmnSum[j] += matrix[i][j]
		maxSum = 0
		for i in range(n):
			maxSum = max(maxSum, rowSum[i])
			maxSum = max(maxSum, coulmnSum[i])
		count = 0
		i = 0
		j = 0
		while i < n and j < n:
			minDiff = min(maxSum - rowSum[i], maxSum - coulmnSum[j])
			matrix[i][j] += minDiff
			rowSum[i] += minDiff
			coulmnSum[j] += minDiff
			count += minDiff
			if rowSum[i] == maxSum:
				i += 1
			if coulmnSum[j] == maxSum:
				j += 1
		return count


class Solution:

	def findMinOpeartion(self, matrix, n):
		(rows, cols) = ([], [])
		for i in range(n):
			rows.append(sum(matrix[i]))
		for i in range(n):
			temp = 0
			for j in range(n):
				temp += matrix[j][i]
			cols.append(temp)
		max_sum = max(max(rows), max(cols))
		ans = 0
		for i in range(n):
			for j in range(n):
				if max_sum - rows[i] >= max_sum - cols[j]:
					temp = max_sum - cols[j]
					ans += temp
					cols[j] += temp
					rows[i] += temp
				else:
					temp = max_sum - rows[i]
					ans += temp
					cols[j] += temp
					rows[i] += temp
		return ans


class Solution:

	def findMinOpeartion(self, matrix, n):
		m = 0
		t = 0
		for i in range(n):
			a = 0
			b = 0
			for j in range(n):
				a += matrix[i][j]
				b += matrix[j][i]
			m = max(m, a, b)
			t += a
		m = m * n
		return m - t


class Solution:

	def findMinOpeartion(self, matrix, n):
		q_row = []
		q_col = []
		ans = 0
		import heapq
		for i in range(len(matrix)):
			s = 0
			for j in range(len(matrix[0])):
				s = s + matrix[i][j]
			heapq.heappush(q_row, s)
			ans = max(ans, s)
		for j in range(len(matrix[0])):
			s = 0
			for i in range(len(matrix)):
				s = s + matrix[i][j]
			heapq.heappush(q_col, s)
			ans = max(ans, s)
		res = 0
		while q_row and q_col:
			temp_r = heapq.heappop(q_row)
			temp_c = heapq.heappop(q_col)
			if temp_c == temp_r:
				res = res + (ans - temp_c)
				continue
			if temp_c > temp_r:
				res = res + (ans - temp_c)
				heapq.heappush(q_row, temp_r - (ans - temp_c))
				continue
			if temp_c < temp_r:
				res = res + (ans - temp_r)
				heapq.heappush(q_col, temp_c - (ans - temp_r))
				continue
			if temp_r + 1 != ans:
				heapq.heappush(q_row, temp_r + 1)
			if temp_c + 1 != ans:
				heapq.heappush(q_col, temp_c + 1)
			res += 1
		return res


class Solution:

	def findMinOpeartion(self, matrix, n):
		maxi = 0
		row_sums = [0] * n
		col_sums = [0] * n
		isRow = True
		for i in range(n):
			rsum = 0
			csum = 0
			for j in range(n):
				rsum += matrix[i][j]
				csum += matrix[j][i]
			row_sums[i] = rsum
			if rsum > maxi:
				maxi = rsum
				isRow = True
			col_sums[i] = csum
			if csum > maxi:
				maxi = csum
				isRow = False
		ans = 0
		if isRow:
			for i in row_sums:
				ans += maxi - i
		else:
			for i in col_sums:
				ans += maxi - i
		return ans


class Solution:

	def findMinOpeartion(self, matrix, n):
		rowsum = [0] * n
		colsum = [0] * n
		for i in range(n):
			for j in range(n):
				rowsum[i] += matrix[i][j]
				colsum[j] += matrix[i][j]
		maxs = 0
		for i in range(n):
			maxs = max(maxs, rowsum[i])
			maxs = max(maxs, colsum[i])
		res = 0
		for i in range(n):
			for j in range(n):
				diff = min(maxs - rowsum[i], maxs - colsum[j])
				res += diff
				rowsum[i] += diff
				colsum[j] += diff
				matrix[i][j] += diff
		return res


class Solution:

	def findMinOpeartion(self, arr, n):
		rowSum = [0] * n
		colSum = [0] * n
		for i in range(n):
			for j in range(n):
				rowSum[i] += arr[i][j]
				colSum[j] += arr[i][j]
		maxSum = max(max(rowSum), max(colSum))
		i = j = opCount = 0
		while i < n and j < n:
			diff = min(maxSum - rowSum[i], maxSum - colSum[j])
			arr[i][j] += diff
			rowSum[i] += diff
			colSum[j] += diff
			opCount += diff
			if rowSum[i] == maxSum:
				i += 1
			if colSum[j] == maxSum:
				j += 1
		return opCount


class Solution:

	def findMinOpeartion(self, matrix, n):
		if n == 1:
			return 0
		(highest_sum, s) = (0, 0)
		for i in range(n):
			s = 0
			for j in range(n):
				s += matrix[i][j]
			highest_sum = max(highest_sum, s)
		for j in range(n):
			s = 0
			for i in range(n):
				s += matrix[i][j]
			highest_sum = max(highest_sum, s)
		res_s = highest_sum * n
		s = 0
		for i in range(n):
			for j in range(n):
				s = s + matrix[i][j]
		return res_s - s


class Solution:

	def findMinOpeartion(self, matrix, n):
		sumRow = [0] * n
		sumCol = [0] * n
		for i in range(n):
			for j in range(n):
				sumRow[i] += matrix[i][j]
				sumCol[j] += matrix[i][j]
		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:
			diff = min(maxSum - sumRow[i], maxSum - sumCol[j])
			matrix[i][j] += diff
			sumRow[i] += diff
			sumCol[j] += diff
			count += diff
			if sumRow[i] == maxSum:
				i += 1
			if sumCol[j] == maxSum:
				j += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		matrix = [[0 for j in range(n)] for i in range(n)]
		line1 = [int(x) for x in input().strip().split()]
		k = 0
		for i in range(n):
			for j in range(n):
				matrix[i][j] = line1[k]
				k += 1
		obj = Solution()
		print(obj.findMinOpeartion(matrix, n))


class Solution:

	def findMinOpeartion(self, a, n):
		max_sum = 0
		total_sum = 0
		for i in range(n):
			col_sum = 0
			row_sum = 0
			for j in range(n):
				col_sum += a[i][j]
				row_sum += a[j][i]
				total_sum += a[i][j]
			max_sum = max(col_sum, row_sum, max_sum)
		return n * max_sum - total_sum
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		matrix = [[0 for j in range(n)] for i in range(n)]
		line1 = [int(x) for x in input().strip().split()]
		k = 0
		for i in range(n):
			for j in range(n):
				matrix[i][j] = line1[k]
				k += 1
		obj = Solution()
		print(obj.findMinOpeartion(matrix, n))


class Solution:

	def findMinOpeartion(self, mat, n):
		calSum = [0 for i in range(len(mat))]
		rowSum = [0 for i in range(len(mat))]
		totalsum = 0
		for i in range(len(mat)):
			for j in range(len(mat)):
				calSum[i] += mat[j][i]
				rowSum[i] += mat[i][j]
				totalsum += mat[i][j]
		mx = max(max(calSum), max(rowSum))
		totalsum_requres = mx * n
		return totalsum_requres - totalsum


class Solution:

	def findMinOpeartion(self, matrix, n):
		rowsum = []
		columnsum = [0 for i in range(n)]
		maxsum = -float('inf')
		for i in range(n):
			sumsofar = 0
			for j in range(n):
				sumsofar += matrix[i][j]
				columnsum[j] += matrix[i][j]
				if i == n - 1:
					maxsum = max(maxsum, columnsum[j])
			rowsum.append(sumsofar)
			maxsum = max(maxsum, sumsofar)
		count = 0
		for i in range(n):
			for j in range(n):
				rowdiff = maxsum - rowsum[i]
				columndiff = maxsum - columnsum[j]
				increment = min(rowdiff, columndiff)
				if increment:
					count += increment
					rowsum[i] += increment
					columnsum[j] += increment
		return count


class Solution:

	def findMinOpeartion(self, matrix, n):
		transpose = list(map(list, zip(*matrix)))
		max_row = sum(matrix[0])
		max_col = sum(transpose[0])
		sum_row = 0
		sum_col = 0
		for k in range(n):
			if max_row < sum(matrix[k]):
				max_row = sum(matrix[k])
			if max_col < sum(transpose[k]):
				max_col = sum(transpose[k])
		for k in range(n):
			sum_row += max_row - sum(matrix[k])
			sum_col += max_col - sum(transpose[k])
		return max(sum_row, sum_col)


class Solution:

	def findMinOpeartion(self, matrix, n):
		cnt = 0
		ma = 0
		for i in range(n):
			val = sum(matrix[i])
			cnt += val
			ma = max(ma, val)
		tot = n * ma - cnt
		cnt = 0
		ma = 0
		for i in range(n):
			val = 0
			for j in range(n):
				val += matrix[j][i]
			cnt += val
			ma = max(ma, val)
		tot2 = n * ma - cnt
		return max(tot, tot2)


class Solution:

	def findMinOpeartion(self, matrix, n):
		i = j = 0
		maxi = 0
		res = 0
		for i in range(0, n):
			rowsum = 0
			colsum = 0
			for j in range(0, n):
				rowsum += matrix[i][j]
			for j in range(0, n):
				colsum += matrix[j][i]
			maxi = max(maxi, max(rowsum, colsum))
		for i in range(0, n):
			rowsum = 0
			for j in range(0, n):
				rowsum += matrix[i][j]
			res += maxi - rowsum
		return res