Dada una array de enteros arr[] de tamaño N , la tarea es encontrar el número mínimo de elementos de array necesarios para dividir por 2, para hacer que al menos K elementos en la array sean iguales.
Ejemplo :
Entrada: arr[] = {1, 2, 2, 4, 5}, N = 5, K = 3
Salida: 1
Explicación:
Dividir 4 por 2 modifica la array a {1, 2, 2, 2, 5} con 3 elementos iguales.
Entrada: arr[] = {1, 2, 3, 4, 5}, N = 5, K = 3
Salida: 1
Explicación:
Dividir 2 y 3 por 2 modifica la array a {1, 1, 1, 4, 5 } con 3 elementos iguales.
Enfoque:
cada entero X se puede dividir por 2 log 2 (X) veces para obtener un valor distinto de cero. Por lo tanto, necesitamos realizar estas operaciones log 2 (arr[i]) en cada elemento del arreglo arr[i] y para cada valor obtenido después de una división, almacenar el número de operaciones requeridas para alcanzar el valor respectivo. Una vez que se hayan realizado todas las operaciones para todos los elementos de la array, para cada valor al que se hayan reducido al menos K elementos de la array en algún momento, encuentre la suma de las K operaciones más pequeñas requeridas entre todas ellas. Encuentre el número mínimo de operaciones requeridas entre todas esas instancias.
Ilustración:
arr[] = {1, 2, 2, 4, 5}, N = 5, K = 3
Solo 1 elemento puede tener un valor de 5, así que ignórelo.
Solo 1 elemento puede tener un valor de 4, así que ignórelo.
Ningún elemento puede tener un valor 3.
4 elementos pueden tener un valor 2.
{1, 2, 2, (4/2), (5/2) } -> {1, 2, 2, 2, 2}
Dado que, el número de posibilidades excede K, encuentre la suma de las K operaciones más pequeñas.
arr[1] -> 0 operaciones
arr[2] -> 0 operaciones
arr[3] -> 1 operación
arr[4] -> 1 operación
Por lo tanto, la suma de las 3 operaciones más pequeñas = (0 + 0 + 1) = 1
Todo 5 elementos se pueden reducir a 1.
{1, 2/2, 2/2, (4/2)/2, (5/2)/2} -> {1, 1, 1, 1, 1}
Por lo tanto, la suma de las 3 operaciones más pequeñas = (0 + 1 + 1) = 2
Por lo tanto, el número mínimo de operaciones requeridas para igualar al menos K elementos es 1.
Siga los pasos a continuación para resolver el problema utilizando el enfoque anterior:
- Cree una array vals[][] tal que vals [ X ][ j ] almacene el número de operaciones necesarias para obtener el valor X de un elemento de array.
- Atraviesa la array y para cada elemento de la array:
- Inicializar x = arr[i]. Inicialice el recuento de operaciones cur como 0.
- En cada paso, actualice x = x/2 e incremente cur en 1 . Inserte cur en vals[x] como el número de divisiones requeridas para obtener el valor actual de x .
- Ahora, todos los valores posibles que se pueden obtener mediante la división repetitiva de cada arr[i] por 2 con el número de divisiones requeridas para obtener ese valor se almacenan en la array vals[][] .
- Ahora, recorra la array vals[][] y para cada fila, realice lo siguiente:
- Compruebe si la fila actual vals[i] consta de al menos K elementos o no. Si vals[i] < K , ignórelo ya que al menos K elementos de la array no se pueden reducir a i .
- Si vals[i].size() es ≥ K , calcule la suma de la fila i . Actualice ans = min(ans, sum of vals[i]) .
- El valor final de ans nos da la respuesta deseada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to make atleast
// K elements of the given array
// equal by dividing by 2
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// minimum number of divisions
// required
int get_min_opration(int arr[], int N,
int K)
{
vector<vector<int> > vals(200001);
for (int i = 0; i < N; ++i) {
int x = arr[i];
int cur = 0;
while (x > 0) {
// cur: number of
// times a[i] is
// divided by 2
// to obtain x
vals[x].push_back(cur);
x /= 2;
++cur;
}
}
int ans = INT_MAX;
for (int i = 0; i <= 200000; ++i) {
// To obtain minimum
// number of operations
sort(vals[i].begin(),
vals[i].end());
}
for (int i = 0; i <= 200000; ++i) {
// If it is not possible
// to make at least K
// elements equal to vals[i]
if (int(vals[i].size()) < K)
continue;
// Store the number
// of operations
int sum = 0;
for (int j = 0; j < K; j++) {
sum += vals[i][j];
}
// Update the minimum
// number of operations
// required
ans = min(ans, sum);
}
return ans;
}
// Driver Program
int main()
{
int N = 5, K = 3;
int arr[] = { 1, 2, 2, 4, 5 };
cout << get_min_opration(arr, N, K);
return 0;
}
Java
// Java program to make atleast
// K elements of the given array
// equal by dividing by 2
import java.util.*;
class GFG{
// Function to return the
// minimum number of divisions
// required
static int get_min_opration(int arr[],
int N, int K)
{
Vector<Integer> []vals = new Vector[200001];
for (int i = 0; i < vals.length; i++)
vals[i] = new Vector<Integer>();
for (int i = 0; i < N; ++i)
{
int x = arr[i];
int cur = 0;
while (x > 0)
{
// cur: number of
// times a[i] is
// divided by 2
// to obtain x
vals[x].add(cur);
x /= 2;
++cur;
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i <= 200000; ++i)
{
// To obtain minimum
// number of operations
Collections.sort(vals[i]);
}
for (int i = 0; i <= 200000; ++i)
{
// If it is not possible
// to make at least K
// elements equal to vals[i]
if ((vals[i].size()) < K)
continue;
// Store the number
// of operations
int sum = 0;
for (int j = 0; j < K; j++)
{
sum += vals[i].get(j);
}
// Update the minimum
// number of operations
// required
ans = Math.min(ans, sum);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 5, K = 3;
int arr[] = {1, 2, 2, 4, 5};
System.out.print(get_min_opration(arr, N, K));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to make atleast # K elements of the given array # equal by dividing by 2 import sys # Function to return the # minimum number of divisions # required def get_min_opration(arr, N, K): vals = [[] for _ in range(200001)] for i in range(N): x = arr[i] cur = 0 while (x > 0): # cur: number of times a[i] # is divided by 2 to obtain x vals[x].append(cur) x //= 2 cur += 1 ans = sys.maxsize for i in range(200001): # To obtain minimum # number of operations vals[i] = sorted(vals[i]) for i in range(200001): # If it is not possible # to make at least K # elements equal to vals[i] if (int(len(vals[i])) < K): continue # Store the number # of operations sum = 0 for j in range(K): sum += vals[i][j] # Update the minimum # number of operations # required ans = min(ans, sum) return ans # Driver code if __name__ == '__main__': N = 5 K = 3 arr = [ 1, 2, 2, 4, 5 ] print(get_min_opration(arr, N, K)) # This code is contributed by mohit kumar 29
C#
// C# program to make atleast
// K elements of the given array
// equal by dividing by 2
using System;
using System.Collections.Generic;
class GFG{
// Function to return the
// minimum number of divisions
// required
static int get_min_opration(int []arr,
int N, int K)
{
List<int> []vals =
new List<int>[200001];
for (int i = 0; i < vals.Length; i++)
vals[i] = new List<int>();
for (int i = 0; i < N; ++i)
{
int x = arr[i];
int cur = 0;
while (x > 0)
{
// cur: number of
// times a[i] is
// divided by 2
// to obtain x
vals[x].Add(cur);
x /= 2;
++cur;
}
}
int ans = int.MaxValue;
for (int i = 0; i <= 200000; ++i)
{
// If it is not possible
// to make at least K
// elements equal to vals[i]
if ((vals[i].Count) < K)
continue;
// Store the number
// of operations
int sum = 0;
for (int j = 0; j < K; j++)
{
sum += vals[i][j];
}
// Update the minimum
// number of operations
// required
ans = Math.Min(ans, sum);
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int N = 5, K = 3;
int []arr = {1, 2, 2, 4, 5};
Console.Write(get_min_opration(arr, N, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program to make atleast
// K elements of the given array
// equal by dividing by 2
// Function to return the
// minimum number of divisions
// required
function get_min_opration(arr, N, K) {
var vals = new Array(200001);
for (var i = 0; i < vals.length; i++) vals[i] = [];
for (var i = 0; i < N; ++i) {
var x = arr[i];
var cur = 0;
while (x > 0) {
// cur: number of
// times a[i] is
// divided by 2
// to obtain x
vals[x].push(cur);
x = parseInt(x / 2);
++cur;
}
}
//Max integer value
var ans = 2147483648;
for (var i = 0; i <= 200000; ++i) {
// If it is not possible
// to make at least K
// elements equal to vals[i]
if (vals[i].length < K) continue;
// Store the number
// of operations
var sum = 0;
for (var j = 0; j < K; j++) {
sum += vals[i][j];
}
// Update the minimum
// number of operations
// required
ans = Math.min(ans, sum);
}
return ans;
}
// Driver code
var N = 5,
K = 3;
var arr = [1, 2, 2, 4, 5];
document.write(get_min_opration(arr, N, K));
</script>
1
Complejidad de Tiempo: O (N * log N)
Espacio Auxiliar: O (N * log N)