Dada una array arr[] de tamaño N que consiste en números enteros positivos y un número entero K , la tarea es encontrar el número mínimo de pasos requeridos para hacer que todos los elementos de la array sean iguales de modo que en cada paso, un valor de la array pueda ser seleccionado y decrementado por K . Imprime -1 si la array no se puede igualar.
Ejemplos:
Entrada: arr[] = {12, 9, 15}, K = 3
Salida: 3
Explicación:
Inicialmente: {12, 9, 15}
Después de disminuir K de 15 en la posición 3: [12, 9, 12]
Después de disminuir K desde 12 en la posición 1: [9, 9, 12]
Después de disminuir K desde 12 en la posición 3: [9, 9, 9]
Entrada: arr[] = {10, 9}, K = 2
Salida: -1
Explicación:
Es imposible igualar todos los elementos.
Enfoque: La idea es mantener los elementos de valor mínimo inalterados y contar el número de operaciones de decremento realizadas por los otros elementos para alcanzar este valor mínimo. Se pueden seguir los siguientes pasos para calcular el resultado:
- Encuentre el elemento mínimo minx en la array.
- Una vez que se encuentra el valor mínimo, una variable se mantiene y se inicializa a 0.
- Luego se ejecuta un ciclo sobre todos los elementos, agregando (arr[i]-minx)/K a la variable de decrementos .
- Si se encuentra algún arr[i] tal que arr[i]-minx no es divisible por K, devuelve -1 ya que no se puede reducir al valor mínimo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; #define lli long long int lli solve(lli arr[], lli n, lli k) { lli i, minx = INT_MAX; // Finding the minimum element for (i = 0; i < n; i++) { minx = min(minx, arr[i]); } lli decrements = 0; // Loop over all the elements // and find the difference for (i = 0; i < n; i++) { if ((arr[i] - minx) % k != 0) { return -1; } else { decrements += ((arr[i] - minx) / k); } } // Solution found and returned return decrements; } // Driver code int main() { lli n, k; n = 3; k = 3; lli arr[n] = { 12, 9, 15 }; cout << solve(arr, n, k); }
Java
// Java implementation of the above approach class GFG { static int INT_MAX = Integer.MAX_VALUE ; static int solve(int arr[], int n, int k) { int minx = INT_MAX; int i; // Finding the minimum element for (i = 0; i < n; i++) { minx = Math.min(minx, arr[i]); } int decrements = 0; // Loop over all the elements // and find the difference for (i = 0; i < n; i++) { if ((arr[i] - minx) % k != 0) { return -1; } else { decrements += ((arr[i] - minx) / k); } } // Solution found and returned return decrements; } // Driver code public static void main (String[] args) { int n, k; n = 3; k = 3; int arr[] = { 12, 9, 15 }; System.out.println(solve(arr, n, k)); } } // This code is contributed by AnkitRai01
Python3
# Python3 implementation of the above approach import sys def solve(arr, n, k) : minx = sys.maxsize; # Finding the minimum element for i in range(n) : minx = min(minx, arr[i]); decrements = 0; # Loop over all the elements # and find the difference for i in range(n) : if ((arr[i] - minx) % k != 0) : return -1; else : decrements += ((arr[i] - minx) // k); # Solution found and returned return decrements; # Driver code if __name__ == "__main__" : n = 3; k = 3; arr = [ 12, 9, 15 ]; print(solve(arr, n, k)); # This code is contributed by AnkitRai01
C#
// C# implementation of the above approach using System; class GFG { static int INT_MAX = int.MaxValue ; static int solve(int []arr, int n, int k) { int minx = INT_MAX; int i; // Finding the minimum element for (i = 0; i < n; i++) { minx = Math.Min(minx, arr[i]); } int decrements = 0; // Loop over all the elements // and find the difference for (i = 0; i < n; i++) { if ((arr[i] - minx) % k != 0) { return -1; } else { decrements += ((arr[i] - minx) / k); } } // Solution found and returned return decrements; } // Driver code public static void Main() { int n, k; n = 3; k = 3; int []arr = { 12, 9, 15 }; Console.WriteLine(solve(arr, n, k)); } } // This code is contributed by AnkitRai01
Javascript
<script> // javascript implementation of the above approach var INT_MAX = Number.MAX_VALUE; function solve(arr , n , k) { var minx = INT_MAX; var i; // Finding the minimum element for (i = 0; i < n; i++) { minx = Math.min(minx, arr[i]); } var decrements = 0; // Loop over all the elements // and find the difference for (i = 0; i < n; i++) { if ((arr[i] - minx) % k != 0) { return -1; } else { decrements += ((arr[i] - minx) / k); } } // Solution found and returned return decrements; } // Driver code var n, k; n = 3; k = 3; var arr = [ 12, 9, 15 ]; document.write(solve(arr, n, k)); // This code is contributed by Rajput-Ji. </script>
3
Complejidad del tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA