Dado un entero K y una array de N filas y M columnas, la tarea es encontrar el número mínimo de operaciones necesarias para igualar todos los elementos de la array. En una sola operación, se puede sumar o restar K de cualquier elemento de la array. Imprime -1 si es imposible hacerlo.
Ejemplos:
Entrada: mat[][] = {{2, 4}, {22, 24}}, K = 2
Salida: 20
mat[0][0] = 2 + (10 * K) = 22 … 10 operaciones
mat[ 0][1] = 4 + (9 * K) = 22 … 9 operaciones
mat[1][0] = 22 … Sin operación
mat[1][1] = 24 – K = 22 … 1 operaciones
10 + 9 + 1 = 20Entrada: mat[][] = {
{3, 63, 42},
{18, 12, 12},
{15, 21, 18},
{33, 84, 24}},
K = 3
Salida: 63
Enfoque: dado que solo se nos permite sumar o restar K de cualquier elemento, podemos inferir fácilmente que la mod de todos los elementos con K debe ser igual porque x % K = (x + K) % K = (x – K) % K
Si ese no es el caso, simplemente imprima -1 . De lo contrario, ordene todos los elementos de la array en orden no decreciente y encuentre la mediana de los elementos ordenados. El número mínimo de pasos ocurriría si convertimos todos los elementos para que sean iguales a la mediana. Calcula estos pasos e imprime el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum
// number of operations required
int minOperations(int n, int m, int k,
vector<vector<int> >& matrix)
{
// Create another array to
// store the elements of matrix
vector<int> arr(n * m, 0);
int mod = matrix[0][0] % k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
arr[i * m + j] = matrix[i][j];
// If not possible
if (matrix[i][j] % k != mod) {
return -1;
}
}
}
// Sort the array to get median
sort(arr.begin(), arr.end());
int median = arr[(n * m) / 2];
// To count the minimum operations
int minOperations = 0;
for (int i = 0; i < n * m; ++i)
minOperations += abs(arr[i] - median) / k;
// If there are even elements, then there
// are two medians. We consider the best
// of two as answer.
if ((n * m) % 2 == 0)
{
int median2 = arr[( (n * m) / 2) - 1];
int minOperations2 = 0;
for (int i = 0; i < n * m; ++i)
minOperations2 += abs(arr[i] - median2) / k;
minOperations = min(minOperations, minOperations2);
}
// Return minimum operations required
return minOperations;
}
// Driver code
int main()
{
vector<vector<int> > matrix = { { 2, 4, 6 },
{ 8, 10, 12 },
{ 14, 16, 18 },
{ 20, 22, 24 } };
int n = matrix.size();
int m = matrix[0].size();
int k = 2;
cout << minOperations(n, m, k, matrix);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the minimum
// number of operations required
static int minOperations(int n, int m,
int k, int matrix[][])
{
// Create another array to
// store the elements of matrix
int [] arr = new int[n * m];
int mod = matrix[0][0] % k;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
arr[i * m + j] = matrix[i][j];
// If not possible
if (matrix[i][j] % k != mod)
{
return -1;
}
}
}
// Sort the array to get median
Arrays.sort(arr);
int median = arr[(n * m) / 2];
// To count the minimum operations
int minOperations = 0;
for (int i = 0; i < n * m; ++i)
minOperations += Math.abs(arr[i] - median) / k;
// If there are even elements, then there
// are two medians. We consider the best
// of two as answer.
if ((n * m) % 2 == 0)
{
int median2 = arr[( (n * m) / 2 ) - 1];
int minOperations2 = 0;
for (int i = 0; i < n * m; ++i)
minOperations2 += Math.abs(arr[i] - median2) / k;
minOperations = Math.min(minOperations, minOperations2);
}
// Return minimum operations required
return minOperations;
}
// Driver code
public static void main(String []args)
{
int matrix [][] = { { 2, 4, 6 },
{ 8, 10, 12 },
{ 14, 16, 18 },
{ 20, 22, 24 } };
int n = matrix.length;
int m = matrix[0].length;
int k = 2;
System.out.println(minOperations(n, m, k, matrix));
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the approach # Function to return the minimum # number of operations required def minOperations(n, m, k, matrix): # Create another array to store the # elements of matrix arr = [0] * (n * m) mod = matrix[0][0] % k for i in range(0, n): for j in range(0, m): arr[i * m + j] = matrix[i][j] # If not possible if matrix[i][j] % k != mod: return -1 # Sort the array to get median arr.sort() median = arr[(n * m) // 2] # To count the minimum operations minOperations = 0 for i in range(0, n * m): minOperations += abs(arr[i] - median) // k # If there are even elements, then there # are two medians. We consider the best # of two as answer. if (n * m) % 2 == 0: median2 = arr[( (n * m) // 2 ) - 1] minOperations2 = 0 for i in range(0, n * m): minOperations2 += abs(arr[i] - median2) // k minOperations = min(minOperations, minOperations2) # Return minimum operations required return minOperations # Driver code if __name__ == "__main__": matrix = [[2, 4, 6], [8, 10, 12], [14, 16, 18], [20, 22, 24]] n = len(matrix) m = len(matrix[0]) k = 2 print(minOperations(n, m, k, matrix)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the minimum
// number of operations required
static int minOperations(int n, int m,
int k, int [,]matrix)
{
// Create another array to
// store the elements of matrix
int []arr = new int[n * m];
int mod = matrix[0, 0] % k;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
arr[i * m + j] = matrix[i,j];
// If not possible
if (matrix[i,j] % k != mod)
{
return -1;
}
}
}
// Sort the array to get median
Array.Sort(arr);
int median = arr[(n * m) / 2];
// To count the minimum operations
int minOperations = 0;
for (int i = 0; i < n * m; ++i)
minOperations += Math.Abs(arr[i] - median) / k;
// If there are even elements, then there
// are two medians. We consider the best
// of two as answer.
if ((n * m) % 2 == 0)
{
int median2 = arr[( (n * m) / 2 ) - 1];
int minOperations2 = 0;
for (int i = 0; i < n * m; ++i)
minOperations2 += Math.Abs(arr[i] - median2) / k;
minOperations = Math.Min(minOperations, minOperations2);
}
// Return minimum operations required
return minOperations;
}
// Driver code
public static void Main()
{
int [,]matrix = { { 2, 4, 6 },
{ 8, 10, 12 },
{ 14, 16, 18 },
{ 20, 22, 24 } };
int n = matrix.GetLength(0);
int m = matrix.GetLength(1);
int k = 2;
Console.WriteLine(minOperations(n, m, k, matrix));
}
}
// This code is contributed by Ryuga
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum
// number of operations required
function minOperations(n, m, k, matrix)
{
// Create another array to
// store the elements of matrix
let arr = new Array(n * m);
arr.fill(0);
let mod = matrix[0][0] % k;
for (let i = 0; i < n; ++i)
{
for (let j = 0; j < m; ++j)
{
arr[i * m + j] = matrix[i][j];
// If not possible
if (matrix[i][j] % k != mod)
{
return -1;
}
}
}
// Sort the array to get median
arr.sort(function(a, b){return a - b});
let median = arr[parseInt((n * m) / 2, 10)];
// To count the minimum operations
let minOperations = 0;
for (let i = 0; i < n * m; ++i)
minOperations += parseInt(Math.abs(arr[i] - median) / k, 10);
// If there are even elements, then there
// are two medians. We consider the best
// of two as answer.
if ((n * m) % 2 == 0)
{
let median2 = arr[parseInt((n * m) / 2, 10)];
let minOperations2 = 0;
for (let i = 0; i < n * m; ++i)
minOperations2 += parseInt(Math.abs(arr[i] - median2) / k, 10);
minOperations = Math.min(minOperations, minOperations2);
}
// Return minimum operations required
return minOperations;
}
// Driver code
let matrix = [ [ 2, 4, 6 ],
[ 8, 10, 12 ],
[ 14, 16, 18 ],
[ 20, 22, 24 ] ];
let n = 4;
let m = 3;
let k = 2;
document.write(minOperations(n, m, k, matrix));
// This code is contributed by mukesh07.
</script>
Producción:
36
A continuación se muestra una implementación que también maneja números negativos en la array de entrada:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum
// number of operations required
int minOperations(int n, int m, int k,
vector<vector<int> >& matrix)
{
// Create another array to
// store the elements of matrix
vector<int> arr;
int mod;
// will not work for negative elements, so ..
// adding this
if (matrix[0][0] < 0) {
mod = k - (abs(matrix[0][0]) % k);
}
else {
mod = matrix[0][0] % k;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
arr.push_back(matrix[i][j]);
// adding this to handle negative elements too .
int val = matrix[i][j];
if (val < 0) {
int res = k - (abs(val) % k);
if (res != mod) {
return -1;
}
}
else {
int foo = matrix[i][j];
if (foo % k != mod) {
return -1;
}
}
}
}
// Sort the array to get median
sort(arr.begin(), arr.end());
int median = arr[(n * m) / 2];
// To count the minimum operations
int minOperations = 0;
for (int i = 0; i < n * m; ++i)
minOperations += abs(arr[i] - median) / k;
// If there are even elements, then there
// are two medians. We consider the best
// of two as answer.
if ((n * m) % 2 == 0) {
// changed here as in case of even elements there will be 2 medians
int median2 = arr[((n * m) / 2) - 1];
int minOperations2 = 0;
for (int i = 0; i < n * m; ++i)
minOperations2 += abs(arr[i] - median2) / k;
minOperations = min(minOperations, minOperations2);
}
// Return minimum operations required
return minOperations;
}
// Driver code
int main()
{
vector<vector<int> > matrix = { { 2, 4, 6 },
{ 8, 10, 12 },
{ 14, 16, 18 },
{ 20, 22, 24 } };
int n = matrix.size();
int m = matrix[0].size();
int k = 2;
cout << minOperations(n, m, k, matrix);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the minimum
// number of operations required
public static int minOperations(int n, int m, int k,
int matrix[][])
{
// Create another array to
// store the elements of matrix
Vector<Integer> arr = new Vector<>();
int mod;
// will not work for negative elements, so ..
// adding this
if (matrix[0][0] < 0)
{
mod = k - (Math.abs(matrix[0][0]) % k);
}
else
{
mod = matrix[0][0] % k;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
arr.add(matrix[i][j]);
// adding this to handle
// negative elements too .
int val = matrix[i][j];
if (val < 0)
{
int res = k - (Math.abs(val) % k);
if (res != mod)
{
return -1;
}
}
else
{
int foo = matrix[i][j];
if (foo % k != mod)
{
return -1;
}
}
}
}
// Sort the array to get median
Collections.sort(arr);
int median = arr.get((n * m) / 2);
// To count the minimum operations
int minOperations = 0;
for (int i = 0; i < n * m; ++i)
minOperations += Math.abs(arr.get(i) - median) / k;
// If there are even elements, then there
// are two medians. We consider the best
// of two as answer.
if ((n * m) % 2 == 0)
{
// changed here as in case of
// even elements there will be 2 medians
int median2 = arr.get(((n * m) / 2) - 1);
int minOperations2 = 0;
for (int i = 0; i < n * m; ++i)
minOperations2 += Math.abs(arr.get(i) - median2) / k;
minOperations = Math.min(minOperations, minOperations2);
}
// Return minimum operations required
return minOperations;
}
// Driver code
public static void main(String[] args)
{
int matrix[][] = {
{2, 4, 6},
{8, 10, 12},
{14, 16, 18},
{20, 22, 24}
};
int n = matrix.length;
int m = matrix[0].length;
int k = 2;
System.out.println(minOperations(n, m, k, matrix));
}
}
// This code is contributed by divyesh072019
Python3
# Python3 implementation of the # above approach # Function to return the minimum # number of operations required def minOperations(n, m, k, matrix): # Create another array to # store the elements of # matrix arr = [] # will not work for negative # elements, so .. adding this if (matrix[0][0] < 0): mod = k - (abs(matrix[0][0]) % k) else: mod = matrix[0][0] % k for i in range(n): for j in range(m): arr.append(matrix[i][j]) # adding this to handle # negative elements too . val = matrix[i][j] if (val < 0): res = k - (abs(val) % k) if (res != mod): return -1 else: foo = matrix[i][j] if (foo % k != mod): return -1 # Sort the array to get median arr.sort() median = arr[(n * m) // 2] # To count the minimum # operations minOperations = 0 for i in range(n * m): minOperations += abs(arr[i] - median) // k # If there are even elements, # then there are two medians. # We consider the best of two # as answer. if ((n * m) % 2 == 0): # changed here as in case of # even elements there will be # 2 medians median2 = arr[((n * m) // 2) - 1] minOperations2 = 0 for i in range(n * m): minOperations2 += abs(arr[i] - median2) / k minOperations = min(minOperations, minOperations2) # Return minimum operations required return minOperations # Driver code if __name__ == "__main__": matrix = [[2, 4, 6], [8, 10, 12], [14, 16, 18], [20, 22, 24]] n = len(matrix) m = len(matrix[0]) k = 2 print(minOperations(n, m, k, matrix)) # This code is contributed by Chitranayal
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG {
// Function to return the minimum
// number of operations required
static int minOperations(int n, int m, int k,
List<List<int>> matrix)
{
// Create another array to
// store the elements of matrix
List<int> arr = new List<int>();
int mod;
// will not work for negative elements, so ..
// adding this
if (matrix[0][0] < 0) {
mod = k - (Math.Abs(matrix[0][0]) % k);
}
else {
mod = matrix[0][0] % k;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
arr.Add(matrix[i][j]);
// adding this to handle negative elements too .
int val = matrix[i][j];
if (val < 0) {
int res = k - (Math.Abs(val) % k);
if (res != mod) {
return -1;
}
}
else {
int foo = matrix[i][j];
if (foo % k != mod) {
return -1;
}
}
}
}
// Sort the array to get median
arr.Sort();
int median = arr[(n * m) / 2];
// To count the minimum operations
int minOperations = 0;
for (int i = 0; i < n * m; ++i)
minOperations += Math.Abs(arr[i] - median) / k;
// If there are even elements, then there
// are two medians. We consider the best
// of two as answer.
if ((n * m) % 2 == 0) {
// changed here as in case of
// even elements there will be 2 medians
int median2 = arr[((n * m) / 2) - 1];
int minOperations2 = 0;
for (int i = 0; i < n * m; ++i)
minOperations2 += Math.Abs(arr[i] - median2) / k;
minOperations = Math.Min(minOperations, minOperations2);
}
// Return minimum operations required
return minOperations;
}
static void Main() {
List<List<int>> matrix = new List<List<int>>{
new List<int> {2, 4, 6},
new List<int> {8, 10, 12},
new List<int> {14, 16, 18},
new List<int> {20, 22, 24},
};
int n = matrix.Count;
int m = matrix[0].Count;
int k = 2;
Console.Write(minOperations(n, m, k, matrix));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum
// number of operations required
function minOperations(n,m,k,matrix)
{
// Create another array to
// store the elements of matrix
let arr = [];
let mod;
// will not work for negative elements, so ..
// adding this
if (matrix[0][0] < 0)
{
mod = k - (Math.abs(matrix[0][0]) % k);
}
else
{
mod = matrix[0][0] % k;
}
for (let i = 0; i < n; ++i)
{
for (let j = 0; j < m; ++j)
{
arr.push(matrix[i][j]);
// adding this to handle
// negative elements too .
let val = matrix[i][j];
if (val < 0)
{
let res = k - (Math.abs(val) % k);
if (res != mod)
{
return -1;
}
}
else
{
let foo = matrix[i][j];
if (foo % k != mod)
{
return -1;
}
}
}
}
// Sort the array to get median
arr.sort(function(a,b){return a-b;});
let median = arr[(n * m) / 2];
// To count the minimum operations
let minOperations = 0;
for (let i = 0; i < n * m; ++i)
minOperations += Math.abs(arr[i] - median) / k;
// If there are even elements, then there
// are two medians. We consider the best
// of two as answer.
if ((n * m) % 2 == 0)
{
// changed here as in case of
// even elements there will be 2 medians
let median2 = arr[((n * m) / 2) - 1];
let minOperations2 = 0;
for (let i = 0; i < n * m; ++i)
minOperations2 += Math.abs(arr[i] - median2) / k;
minOperations = Math.min(minOperations, minOperations2);
}
// Return minimum operations required
return minOperations;
}
// Driver code
let matrix = [[2, 4, 6],
[8, 10, 12],
[14, 16, 18],
[20, 22, 24]];
let n = matrix.length;
let m = matrix[0].length;
let k = 2;
document.write(minOperations(n, m, k, matrix));
// This code is contributed by rag2127
</script>
Producción:
36
Publicación traducida automáticamente
Artículo escrito por NaimishSingh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA