Minimice el recuento de divisiones por D para obtener al menos K elementos de array iguales

Dada una array A[ ] de tamaño N y dos enteros K y D , la tarea es calcular el número mínimo posible de operaciones requeridas para obtener al menos K elementos de array iguales. Cada operación implica reemplazar un elemento A[i] por A[i] / D . Esta operación se puede realizar cualquier número de veces.

Ejemplos: 

Entrada: N = 5, A[ ] = {1, 2, 3, 4, 5}, K = 3, D = 2 
Salida: 2 
Explicación: 
Paso 1: Reemplace A[3] por A[3] / D, es decir, (4/2) = 2. Por lo tanto, la array se modifica a {1, 2, 3, 2, 5} 
Paso 2: Reemplace A[4] por A[4] / D, es decir, (5/2) = 2 Por lo tanto, la array se modifica a {1, 2, 3, 2, 2} 
Por lo tanto, la array modificada tiene K (= 3) elementos iguales. 
Por lo tanto, el número mínimo de operaciones requeridas es 2.

Entrada: N = 4, A[ ] = {1, 2, 3, 6}, K = 2, D = 3 
Salida: 1 
Explicación:
Reemplazar A[3] por A[3] / D, es decir (6 / 3 ) = 2. Por lo tanto, la array se modifica a {1, 2, 3, 2}. 
Por lo tanto, la array modificada tiene K(= 2) elementos iguales. 
Por lo tanto, el número mínimo de operaciones requeridas es 1. 

Enfoque ingenuo: 
el enfoque más simple para resolver el problema es generar todos los subconjuntos posibles de la array dada y realizar la operación dada en todos los elementos de este subconjunto. El número de operaciones necesarias para cada subconjunto será igual al tamaño del subconjunto. Para cada subconjunto, cuente el número de elementos iguales y verifique si count es igual a K . Si es así, compare el recuento con los movimientos mínimos obtenidos hasta el momento y actualice en consecuencia. Finalmente, imprime los movimientos mínimos.

Complejidad temporal: O(2 ^N *N) 
Espacio auxiliar: O(N)

Enfoque eficiente: 
siga los pasos a continuación para resolver el problema: 

• Inicialice un vector 2D V , en el que el tamaño de una fila V[i] indica el número de elementos de array que se han reducido a A[i] y cada elemento de la fila indica un recuento de divisiones por D realizadas en un elemento de array para obtener el número i .
• Atraviesa la array. Para cada elemento A[i] , siga dividiéndolo por D hasta que se reduzca a 0 .
• Para cada valor intermedio de A[i] obtenido en el paso anterior, inserte el número de divisiones requeridas en V[A[i]] .
• Una vez que haya completado los pasos anteriores para toda la array, itere sobre la array V[ ] .
• Para cada V[i], verifique si el tamaño de V[i] ≥ K (como máximo K).
• Si V[i] ≥ K , indica que al menos K elementos en la array se han reducido a i . Ordene V[i] y agregue los primeros valores K , es decir, los K movimientos más pequeños necesarios para hacer que los elementos K sean iguales en la array.
• Compare la suma de K movimientos con los movimientos mínimos requeridos y actualice en consecuencia.
• Una vez que se completa el recorrido de la array V[] , imprima el recuento mínimo de movimientos obtenido finalmente.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return minimum
// number of moves required
int getMinimumMoves(int n, int k, int d,
                    vector<int> a)
{
    int MAX = 100000;
 
    // Stores the number of moves
    // required to obtain respective
    // values from the given array
    vector<int> v[MAX];
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
        int cnt = 0;
 
        // Insert 0 into V[a[i]] as
        // it is the initial state
        v[a[i]].push_back(0);
 
        while (a[i] > 0) {
            a[i] /= d;
            cnt++;
 
            // Insert the moves required
            // to obtain current a[i]
            v[a[i]].push_back(cnt);
        }
    }
 
    int ans = INT_MAX;
 
    // Traverse v[] to obtain
    // minimum count of moves
    for (int i = 0; i < MAX; i++) {
 
        // Check if there are at least
        // K equal elements for v[i]
        if (v[i].size() >= k) {
 
            int move = 0;
 
            sort(v[i].begin(), v[i].end());
 
            // Add the sum of minimum K moves
            for (int j = 0; j < k; j++) {
 
                move += v[i][j];
            }
 
            // Update answer
            ans = min(ans, move);
        }
    }
 
    // Return the final answer
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5, K = 3, D = 2;
    vector<int> A = { 1, 2, 3, 4, 5 };
 
    cout << getMinimumMoves(N, K, D, A);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to return minimum
// number of moves required
@SuppressWarnings("unchecked")
static int getMinimumMoves(int n, int k,
                           int d, int[] a)
{
    int MAX = 100000;
 
    // Stores the number of moves
    // required to obtain respective
    // values from the given array
    Vector<Integer> []v = new Vector[MAX];
    for(int i = 0; i < v.length; i++)
        v[i] = new Vector<Integer>();
         
    // Traverse the array
    for(int i = 0; i < n; i++)
    {
        int cnt = 0;
 
        // Insert 0 into V[a[i]] as
        // it is the initial state
        v[a[i]].add(0);
 
        while (a[i] > 0)
        {
            a[i] /= d;
            cnt++;
 
            // Insert the moves required
            // to obtain current a[i]
            v[a[i]].add(cnt);
        }
    }
 
    int ans = Integer.MAX_VALUE;
 
    // Traverse v[] to obtain
    // minimum count of moves
    for(int i = 0; i < MAX; i++)
    {
         
        // Check if there are at least
        // K equal elements for v[i]
        if (v[i].size() >= k)
        {
            int move = 0;
 
            Collections.sort(v[i]);
 
            // Add the sum of minimum K moves
            for(int j = 0; j < k; j++)
            {
                move += v[i].get(j);
            }
 
            // Update answer
            ans = Math.min(ans, move);
        }
    }
 
    // Return the final answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5, K = 3, D = 2;
    int []A = { 1, 2, 3, 4, 5 };
 
    System.out.print(getMinimumMoves(N, K, D, A));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to implement
# the above approach
 
# Function to return minimum
# number of moves required
def getMinimumMoves(n, k, d, a):
 
    MAX = 100000
 
    # Stores the number of moves
    # required to obtain respective
    # values from the given array
    v = []
    for i in range(MAX):
        v.append([])
 
    # Traverse the array
    for i in range(n):
        cnt = 0
 
        # Insert 0 into V[a[i]] as
        # it is the initial state
        v[a[i]] += [0]
 
        while(a[i] > 0):
            a[i] //= d
            cnt += 1
 
            # Insert the moves required
            # to obtain current a[i]
            v[a[i]] += [cnt]
 
    ans = float('inf')
 
    # Traverse v[] to obtain
    # minimum count of moves
    for i in range(MAX):
 
        # Check if there are at least
        # K equal elements for v[i]
        if(len(v[i]) >= k):
            move = 0
            v[i].sort()
 
            # Add the sum of minimum K moves
            for j in range(k):
                move += v[i][j]
 
            # Update answer
            ans = min(ans, move)
 
    # Return the final answer
    return ans
 
# Driver Code
if __name__ == '__main__':
 
    N = 5
    K = 3
    D = 2
    A = [ 1, 2, 3, 4, 5 ]
 
    # Function call
    print(getMinimumMoves(N, K, D, A))
 
# This code is contributed by Shivam Singh

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to return minimum
// number of moves required
 
static int getMinimumMoves(int n, int k,
                           int d, int[] a)
{
    int MAX = 100000;
 
    // Stores the number of moves
    // required to obtain respective
    // values from the given array
    List<int> []v = new List<int>[MAX];
    for(int i = 0; i < v.Length; i++)
        v[i] = new List<int>();
         
    // Traverse the array
    for(int i = 0; i < n; i++)
    {
        int cnt = 0;
 
        // Insert 0 into V[a[i]] as
        // it is the initial state
        v[a[i]].Add(0);
 
        while (a[i] > 0)
        {
            a[i] /= d;
            cnt++;
 
            // Insert the moves required
            // to obtain current a[i]
            v[a[i]].Add(cnt);
        }
    }
 
    int ans = int.MaxValue;
 
    // Traverse v[] to obtain
    // minimum count of moves
    for(int i = 0; i < MAX; i++)
    {
         
        // Check if there are at least
        // K equal elements for v[i]
        if (v[i].Count >= k)
        {
            int move = 0;
 
            v[i].Sort();
 
            // Add the sum of minimum K moves
            for(int j = 0; j < k; j++)
            {
                move += v[i][j];
            }
 
            // Update answer
            ans = Math.Min(ans, move);
        }
    }
 
    // Return the final answer
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 5, K = 3, D = 2;
    int []A = { 1, 2, 3, 4, 5 };
 
    Console.Write(getMinimumMoves(N, K, D, A));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript Program to implement
// the above approach
 
 
// Function to return minimum
// number of moves required
function getMinimumMoves(n, k, d,a)
{
    let MAX = 100000;
 
    // Stores the number of moves
    // required to obtain respective
    // values from the given array
    let v = new Array(MAX).fill(0).map(()=>new Array());
 
    // Traverse the array
    for (let i = 0; i < n; i++) {
        let cnt = 0;
 
        // Insert 0 into V[a[i]] as
        // it is the initial state
        v[a[i]].push(0);
 
        while (a[i] > 0) {
            a[i] = Math.floor(a[i] / d);
            cnt++;
 
            // Insert the moves required
            // to obtain current a[i]
            v[a[i]].push(cnt);
        }
    }
 
    let ans = Number.MAX_VALUE;
 
    // Traverse v[] to obtain
    // minimum count of moves
    for (let i = 0; i < MAX; i++) {
 
        // Check if there are at least
        // K equal elements for v[i]
        if (v[i].length >= k) {
 
            let move = 0;
 
            v[i].sort((a,b)=>a-b);
 
            // Add the sum of minimum K moves
            for (let j = 0; j < k; j++) {
 
                move += v[i][j];
            }
 
            // Update answer
            ans = Math.min(ans, move);
        }
    }
 
    // Return the final answer
    return ans;
}
 
// driver code
 
let N = 5, K = 3, D = 2;
let A = [ 1, 2, 3, 4, 5 ];
 
document.write(getMinimumMoves(N, K, D, A),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

2

Complejidad de Tiempo: O(MlogM), donde M es el número máximo tomado 
Espacio Auxiliar: O(M)