Operaciones de decremento mínimo para hacer que los elementos de Array sean iguales al solo disminuir K cada vez

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: 
 

1. Encuentre el elemento mínimo minx en la array.
2. Una vez que se encuentra el valor mínimo, una variable se mantiene y se inicializa a 0.
3. Luego se ejecuta un ciclo sobre todos los elementos, agregando (arr[i]-minx)/K a la variable de decrementos .
4. 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++ 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 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 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# 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

<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)