Dada una array arr[] de longitud N y un entero K . En cada operación, se puede seleccionar cualquier elemento (digamos arr[i] ) de la array y se puede cambiar a arr[i] + 1 o arr[i] – 1 . La tarea es encontrar el número mínimo de operaciones requeridas para realizar en la array de modo que cada valor de la array módulo K permanezca igual.
Ejemplos:
Entrada: arr[] = {4, 5, 8, 3, 12}, k =5
Salida: 4
Explicación:
Operación 1: { 3, 5, 8, 3, 12 }, disminuir 4 en el índice 0 en 1.
Operación 2: { 3, 4, 8, 3, 12 }, disminuir 5 en el índice 1 en 1.
Operación 3: { 3, 3, 8, 3, 12 }, disminuir 4 en el índice 1 en 1.
Operación 4: { 3 , 3, 8, 3, 13 }, aumente 12 en el índice 4 en 1.
El módulo de cada número es igual a 3 y los pasos mínimos requeridos fueron 4.Entrada: arr[] = {2, 35, 48, 23, 52}, k =3
Salida: 2
Explicación:
El número mínimo de pasos necesarios para igualar el módulo de cada número es 2.
Planteamiento: La idea es utilizar Hashing que lleva la cuenta de cada módulo que se ha obtenido.
- Ahora itere para cada valor de i, en el rango 0 <= i < k, y encuentre el número de operaciones requeridas para igualar el módulo de todos los números.
- Si es menor que el valor obtenido que el valor almacenado actualmente, actualícelo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum operations
// required to make the modulo of each
// element of the array equal to each other
int Find_min(set<int>& diff_mod,
map<int, int> count_mod, int k)
{
// Variable to store minimum
// operation required
int min_oprn = INT_MAX;
// To store operation required to
// make all modulo equal
int oprn = 0;
// Iterating through all
// possible modulo value
for (int x = 0; x < k; x++) {
oprn = 0;
// Iterating through all different
// modulo obtained so far
for (auto w : diff_mod) {
// Calculating oprn required
// to make all modulos equal
// to x
if (w != x) {
if (w == 0) {
// Checking the operations
// that will cost less
oprn += min(x, k - x)
* count_mod[w];
}
else {
// Check operation that
// will cost less
oprn += min(
abs(x - w),
k + x - w)
* count_mod[w];
}
}
}
// Update the minimum
// number of operations
if (oprn < min_oprn)
min_oprn = oprn;
}
// Returning the answer
return min_oprn;
}
// Function to store different modulos
int Cal_min(int arr[], int n, int k)
{
// Set to store all
// different modulo
set<int> diff_mod;
// Map to store count
// of all different modulo
// obtained
map<int, int> count_mod;
// Storing all different
// modulo count
for (int i = 0; i < n; i++) {
// Insert into the set
diff_mod.insert(arr[i] % k);
// Increment count
count_mod[arr[i] % k]++;
}
// Function call to return value of
// min oprn required
return Find_min(diff_mod, count_mod, k);
}
// Driver Code
int main()
{
int arr[] = { 2, 35, 48, 23, 52 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << Cal_min(arr, n, k);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum operations
// required to make the modulo of each
// element of the array equal to each other
static int Find_min(HashSet<Integer> diff_mod,
HashMap<Integer,
Integer> count_mod,
int k)
{
// Variable to store minimum
// operation required
int min_oprn = Integer.MAX_VALUE;
// To store operation required to
// make all modulo equal
int oprn = 0;
// Iterating through all
// possible modulo value
for(int x = 0; x < k; x++)
{
oprn = 0;
// Iterating through all different
// modulo obtained so far
for(int w : diff_mod)
{
// Calculating oprn required
// to make all modulos equal
// to x
if (w != x)
{
if (w == 0)
{
// Checking the operations
// that will cost less
oprn += Math.min(x, k - x) *
count_mod.get(w);
}
else
{
// Check operation that
// will cost less
oprn += Math.min(Math.abs(x - w),
k + x - w) *
count_mod.get(w);
}
}
}
// Update the minimum
// number of operations
if (oprn < min_oprn)
min_oprn = oprn;
}
// Returning the answer
return min_oprn;
}
// Function to store different modulos
static int Cal_min(int arr[], int n, int k)
{
// Set to store all
// different modulo
HashSet<Integer> diff_mod = new HashSet<>();
// Map to store count
// of all different modulo
// obtained
HashMap<Integer,
Integer> count_mod = new HashMap<>();
// Storing all different
// modulo count
for(int i = 0; i < n; i++)
{
// Insert into the set
diff_mod.add(arr[i] % k);
// Increment count
count_mod.put(arr[i] % k,
count_mod.getOrDefault(arr[i] % k, 0) + 1);
}
// Function call to return value of
// min oprn required
return Find_min(diff_mod, count_mod, k);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 35, 48, 23, 52 };
int n = arr.length;
int k = 3;
System.out.print(Cal_min(arr, n, k));
}
}
// This code is contributed by jrishabh99
Python3
# Python3 program for # the above approach import sys from collections import defaultdict # Function to find the minimum operations # required to make the modulo of each # element of the array equal to each other def Find_min(diff_mod, count_mod, k): # Variable to store minimum # operation required min_oprn = sys.maxsize # To store operation required to # make all modulo equal oprn = 0 # Iterating through all # possible modulo value for x in range (k): oprn = 0 # Iterating through all different # modulo obtained so far for w in diff_mod: # Calculating oprn required # to make all modulos equal # to x if (w != x): if (w == 0): # Checking the operations # that will cost less oprn += (min(x, k - x) * count_mod[w]) else: # Check operation that # will cost less oprn += (min(abs(x - w), k + x - w) * count_mod[w]) # Update the minimum # number of operations if (oprn < min_oprn): min_oprn = oprn # Returning the answer return min_oprn # Function to store different modulos def Cal_min(arr, n, k): # Set to store all # different modulo diff_mod = set([]) # Map to store count # of all different modulo # obtained count_mod = defaultdict (int) # Storing all different # modulo count for i in range (n): # Insert into the set diff_mod.add(arr[i] % k) # Increment count count_mod[arr[i] % k] += 1 # Function call to return value of # min oprn required return Find_min(diff_mod, count_mod, k) # Driver Code if __name__ == "__main__": arr = [2, 35, 48, 23, 52] n = len(arr) k = 3 print( Cal_min(arr, n, k)) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum operations
// required to make the modulo of each
// element of the array equal to each other
static int Find_min(HashSet<int> diff_mod,
Dictionary<int,
int> count_mod,
int k)
{
// Variable to store minimum
// operation required
int min_oprn = int.MaxValue;
// To store operation required to
// make all modulo equal
int oprn = 0;
// Iterating through all
// possible modulo value
for(int x = 0; x < k; x++)
{
oprn = 0;
// Iterating through all different
// modulo obtained so far
foreach(int w in diff_mod)
{
// Calculating oprn required
// to make all modulos equal
// to x
if (w != x)
{
if (w == 0)
{
// Checking the operations
// that will cost less
oprn += Math.Min(x, k - x) *
count_mod[w];
}
else
{
// Check operation that
// will cost less
oprn += Math.Min(Math.Abs(x - w),
k + x - w) *
count_mod[w];
}
}
}
// Update the minimum
// number of operations
if (oprn < min_oprn)
min_oprn = oprn;
}
// Returning the answer
return min_oprn;
}
// Function to store different modulos
static int Cal_min(int []arr, int n, int k)
{
// Set to store all
// different modulo
HashSet<int> diff_mod = new HashSet<int>();
// Map to store count
// of all different modulo
// obtained
Dictionary<int,
int> count_mod = new Dictionary<int,
int>();
// Storing all different
// modulo count
for(int i = 0; i < n; i++)
{
// Insert into the set
diff_mod.Add(arr[i] % k);
// Increment count
if(count_mod.ContainsKey((arr[i] % k)))
count_mod[arr[i] % k] = count_mod[(arr[i] % k)]+1;
else
count_mod.Add(arr[i] % k, 1);
}
// Function call to return value of
// min oprn required
return Find_min(diff_mod, count_mod, k);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 35, 48, 23, 52 };
int n = arr.Length;
int k = 3;
Console.Write(Cal_min(arr, n, k));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum operations
// required to make the modulo of each
// element of the array equal to each other
function Find_min(diff_mod, count_mod, k)
{
// Variable to store minimum
// operation required
let min_oprn = Number.MAX_VALUE;
// To store operation required to
// make all modulo equal
let oprn = 0;
// Iterating through all
// possible modulo value
for(let x = 0; x < k; x++)
{
oprn = 0;
// Iterating through all different
// modulo obtained so far
for(let w of diff_mod.values())
{
// Calculating oprn required
// to make all modulos equal
// to x
if (w != x)
{
if (w == 0)
{
// Checking the operations
// that will cost less
oprn += Math.min(x, k - x) *
count_mod.get(w);
}
else
{
// Check operation that
// will cost less
oprn += Math.min(Math.abs(x - w),
k + x - w) *
count_mod.get(w);
}
}
}
// Update the minimum
// number of operations
if (oprn < min_oprn)
min_oprn = oprn;
}
// Returning the answer
return min_oprn;
}
// Function to store different modulos
function Cal_min(arr, n, k)
{
// Set to store all
// different modulo
let diff_mod = new Set();
// Map to store count
// of all different modulo
// obtained
let count_mod = new Map();
// Storing all different
// modulo count
for(let i = 0; i < n; i++)
{
// Insert into the set
diff_mod.add(arr[i] % k);
// Increment count
// Increment count
if(count_mod.has((arr[i] % k)))
count_mod.set(arr[i] % k,
count_mod.get(arr[i] % k) + 1);
else
count_mod.set(arr[i] % k, 1);
}
// Function call to return value of
// min oprn required
return Find_min(diff_mod, count_mod, k);
}
// Driver Code
let arr = [ 2, 35, 48, 23, 52 ];
let n = arr.length;
let k = 3;
document.write(Cal_min(arr, n, k));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad de tiempo: O(N*K)