Dada una array cuadrada de tamaño 
. Encuentre el número mínimo de operaciones que se requieren para que la suma de los elementos en cada fila y columna sea igual. En una operación, incremente cualquier valor de la celda de la array en 1. En la primera línea, imprima la operación mínima requerida y en las siguientes ‘n’ líneas, imprima ‘n’ enteros que representan la array final después de la operación.
Ejemplo:
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
El enfoque es simple, supongamos que maxSum es la suma máxima entre todas las filas y columnas. Solo necesitamos incrementar algunas celdas de modo que la suma de cualquier fila o columna se convierta en ‘maxSum’.
Digamos que X i es el número total de operaciones necesarias para que la suma en la fila ‘i’ sea igual a maxSum e Y j es la cantidad total de operaciones necesarias para que la suma en la columna ‘j’ sea igual a maxSum . Dado que X i = Y j , necesitamos trabajar en cualquiera de ellos de acuerdo con la condición.
Para minimizar Xi, debemos elegir el máximo de rowSum i y colSum j , ya que seguramente conducirá a la operación mínima. Después de eso, incremente ‘i’ o ‘j’ según la condición satisfecha después del incremento.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to Find minimum number of operation required
// such that sum of elements on each row and column becomes
// same*/
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum operation required to make sum
// of each row and column equals
int findMinOpeartion(int matrix[][2], 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[][2], int n)
{
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cout << matrix[i][j] << " ";
cout << "\n";
}
}
// Driver code
int main()
{
int matrix[][2] = { { 1, 2 }, { 3, 4 } };
cout << findMinOpeartion(matrix, 2) << "\n";
printMatrix(matrix, 2);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C Program to Find minimum number of operation required
// such that sum of elements on each row and column becomes
// same
#include <stdio.h>
#include <string.h>
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
// Function to find minimum operation required to make sum
// of each row and column equals
int findMinOpeartion(int matrix[][2], 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[][2], int n)
{
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
printf("%d ", matrix[i][j]);
printf("\n");
}
}
// Driver code
int main()
{
int matrix[][2] = { { 1, 2 }, { 3, 4 } };
printf("%d\n", findMinOpeartion(matrix, 2));
printMatrix(matrix, 2);
return 0;
}
// This code is contributed by Sania Kumari Gupta
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 Sania Kumari Gupta
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.
Javascript
<script>
// Javascript 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
function findMinOpeartion(matrix,n)
{
// Initialize the sumRow[]
// and sumCol[] array to 0
let sumRow = new Array(n);
let sumCol = new Array(n);
for(let i=0;i<n;i++)
{
sumRow[i]=0;
sumCol[i]=0;
}
// Calculate sumRow[] and
// sumCol[] array
for (let i = 0; i < n; ++i)
for (let 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
let maxSum = 0;
for (let i = 0; i < n; ++i)
{
maxSum = Math.max(maxSum, sumRow[i]);
maxSum = Math.max(maxSum, sumCol[i]);
}
let count = 0;
for (let i = 0, j = 0; i < n && j < n;)
{
// Find minimum increment
// required in either row
// or column
let 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
function printMatrix(matrix,n)
{
for (let i = 0; i < n; ++i)
{
for (let j = 0; j < n; ++j)
document.write(matrix[i][j] +
" ");
document.write("<br>");
}
}
/* Driver program */
let matrix=[[1, 2],[3, 4]];
document.write(findMinOpeartion(matrix, 2)+"<br>");
printMatrix(matrix, 2);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
4 4 3 3 4
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Shubham Bansal 13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA