Dada una array a[] , el entero K y un entero X (que inicialmente se inicializa en 0). Nuestra tarea es encontrar el número mínimo de movimientos requeridos para actualizar la array de modo que cada uno de sus elementos sea divisible por K realizando las siguientes operaciones:
- Elija un índice i de 1 a N y aumente a i en X y luego aumente X en 1. Esta operación no se puede aplicar más de una vez a cada elemento de la array
- Solo aumenta el valor de X en 1.
Ejemplos:
Entrada: K = 3, a = [1, 2, 2, 18]
Salida: 5
Explicación:
Inicialmente X = 0, por lo tanto, actualice X a 1.
Para X = 1 agregue X al segundo elemento de la array para hacer la array [1 , 3, 2, 18] y aumente X en 1.
Para X = 2, agregue X al primer elemento de la array [3, 3, 2, 18] y aumente X en 1.
Para X = 3, simplemente aumente X en 1.
Para X = 4 agregue X al tercer elemento de la array para formar la array [3, 3, 6, 18] y aumente X en 1.
Por último, la array se convierte en [3, 3, 6, 18] donde todos los elementos son divisibles por K = 3.
Entrada: K = 5, a[] = [15, 25, 5, 10, 20, 1005, 70, 80, 90, 100]
Salida: 0
Explicación:
Aquí todos los elementos ya son divisibles por 5.
Enfoque: la idea principal es encontrar el valor máximo de X que se necesita para actualizar los elementos de la array para que sea divisible por K.
- Para hacer esto, necesitamos encontrar el valor máximo de (K – (a i mod K)) para agregar a los elementos de la array para que sea divisible por K.
- Sin embargo, puede haber elementos iguales, por lo que debe realizar un seguimiento del número de dichos elementos, utilizando estructuras de datos de mapa .
- Cuando encuentre otro elemento similar en la array, actualice la respuesta con (K – (a i mod K)) + (K * número de elementos iguales) porque con cada movimiento aumentamos X en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// Minimum number of moves required to
// update the array such that each of
// its element is divisible by K
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// Minimum number of moves required to
// update the array such that each of
// its element is divisible by K
void compute(int a[], int N, int K)
{
// Initialize Map data structure
map<long, long> eqVal;
long maxX = 0;
// Iterate for all the elements
// of the array
for (int i = 0; i < N; i++) {
// Calculate the
// value to be added
long val = a[i] % K;
val = (val == 0 ? 0 : K - val);
// Check if the value equals
// to 0 then simply continue
if (val == 0)
continue;
// Check if the value to be
// added is present in the map
if (eqVal.find(val) != eqVal.end()) {
long numVal = eqVal[val];
// Update the answer
maxX = max(maxX,
val + (K * numVal));
eqVal[val]++;
}
else {
eqVal[val]++;
maxX = max(maxX, val);
}
}
// Print the required result
// We need to add 1 to maxX
// because we cant ignore the
// first move where initially X=0
// and we need to increase it by 1
// to make some changes in array
cout << (maxX == 0 ? 0 : maxX + 1)
<< endl;
}
// Driver code
int main()
{
int K = 3;
int a[] = { 1, 2, 2, 18 };
int N = sizeof(a) / sizeof(a[0]);
compute(a, N, K);
return 0;
}
Java
// Java implementation to find the
// minimum number of moves required to
// update the array such that each of
// its element is divisible by K
import java.util.*;
class GFG{
// Function to find the minimum
// number of moves required to
// update the array such that each of
// its element is divisible by K
static void compute(int a[], int N, int K)
{
// Initialize Map data structure
Map<Long,
Long> eqVal = new HashMap<Long,
Long>();
long maxX = 0;
// Iterate for all the elements
// of the array
for(int i = 0; i < N; i++)
{
// Calculate the
// value to be added
long val = a[i] % K;
val = (val == 0 ? 0 : K - val);
// Check if the value equals
// to 0 then simply continue
if (val == 0)
continue;
// Check if the value to be
// added is present in the map
if (eqVal.containsKey(val))
{
long numVal = eqVal.get(val);
// Update the answer
maxX = Math.max(maxX,
val + (K * numVal));
eqVal.put(val,
eqVal.getOrDefault(val, 0l) + 1l);
}
else
{
eqVal.put(val, 1l);
maxX = Math.max(maxX, val);
}
}
// Print the required result
// We need to add 1 to maxX
// because we cant ignore the
// first move where initially X=0
// and we need to increase it by 1
// to make some changes in array
System.out.println(maxX == 0 ? 0 : maxX + 1);
}
// Driver code
public static void main(String[] args)
{
int K = 3;
int a[] = { 1, 2, 2, 18 };
int N = a.length;
compute(a, N, K);
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation to find the # Minimum number of moves required to # update the array such that each of # its element is divisible by K from collections import defaultdict # Function to find the Minimum number # of moves required to update the # array such that each of its # element is divisible by K def compute(a, N, K): # Initialize Map data structure eqVal = defaultdict(int) maxX = 0 # Iterate for all the elements # of the array for i in range(N): # Calculate the # value to be added val = a[i] % K if (val != 0): val = K - val # Check if the value equals # to 0 then simply continue if (val == 0): continue # Check if the value to be # added is present in the map if (val in eqVal): numVal = eqVal[val] # Update the answer maxX = max(maxX, val + (K * numVal)) eqVal[val] += 1 else: eqVal[val] += 1 maxX = max(maxX, val) # Print the required result # We need to add 1 to maxX # because we cant ignore the # first move where initially X=0 # and we need to increase it by 1 # to make some changes in array if maxX == 0: print(0) else: print(maxX + 1) # Driver code if __name__ == "__main__": K = 3 a = [ 1, 2, 2, 18 ] N = len(a) compute(a, N, K) # This code is contributed by chitranayal
C#
// C# implementation to find the
// minimum number of moves required to
// update the array such that each of
// its element is divisible by K
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum
// number of moves required to
// update the array such that each of
// its element is divisible by K
static void compute(int []a, int N, int K)
{
// Initialize Map data structure
Dictionary<long,
long> eqVal = new Dictionary<long,
long>();
long maxX = 0;
// Iterate for all the elements
// of the array
for(int i = 0; i < N; i++)
{
// Calculate the
// value to be added
long val = a[i] % K;
val = (val == 0 ? 0 : K - val);
// Check if the value equals
// to 0 then simply continue
if (val == 0)
continue;
// Check if the value to be
// added is present in the map
if (eqVal.ContainsKey(val))
{
long numVal = eqVal[val];
// Update the answer
maxX = Math.Max(maxX,
val + (K * numVal));
eqVal[val] = 1 +
eqVal.GetValueOrDefault(val, 0);
}
else
{
eqVal.Add(val, 1);
maxX = Math.Max(maxX, val);
}
}
// Print the required result
// We need to add 1 to maxX
// because we cant ignore the
// first move where initially X=0
// and we need to increase it by 1
// to make some changes in array
Console.Write(maxX == 0 ? 0 : maxX + 1);
}
// Driver code
public static void Main(string[] args)
{
int K = 3;
int []a = { 1, 2, 2, 18 };
int N = a.Length;
compute(a, N, K);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation to find the
// minimum number of moves required to
// update the array such that each of
// its element is divisible by K
// Function to find the minimum
// number of moves required to
// update the array such that each of
// its element is divisible by K
function compute(a,N,K)
{
// Initialize Map data structure
let eqVal = new Map();
let maxX = 0;
// Iterate for all the elements
// of the array
for(let i = 0; i < N; i++)
{
// Calculate the
// value to be added
let val = a[i] % K;
val = (val == 0 ? 0 : K - val);
// Check if the value equals
// to 0 then simply continue
if (val == 0)
continue;
// Check if the value to be
// added is present in the map
if (eqVal.has(val))
{
let numVal = eqVal.get(val);
// Update the answer
maxX = Math.max(maxX,
val + (K * numVal));
eqVal.set(val,eqVal.get(val) + 1);
}
else
{
eqVal.set(val, 1);
maxX = Math.max(maxX, val);
}
}
// Print the required result
// We need to add 1 to maxX
// because we cant ignore the
// first move where initially X=0
// and we need to increase it by 1
// to make some changes in array
document.write(maxX == 0 ? 0 : maxX + 1);
}
// Driver code
let K = 3;
let a=[1, 2, 2, 18];
let N = a.length;
compute(a, N, K);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
5
Complejidad de tiempo: O(N*logN), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(N), donde N representa el tamaño de la array dada.
Publicación traducida automáticamente
Artículo escrito por rudenkoruslan846 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA