Dada una array arr[] que consta de N enteros positivos y un entero K , la tarea es minimizar el valor máximo de la array dividiendo el elemento de la array en potencias de 2 como máximo K veces.
Ejemplos:
Entrada: arr[] = {2, 4, 11, 2}, K = 2
Salida: 2
Explicación:
A continuación se muestran las operaciones realizadas en los elementos de la array como máximo K(= 2) veces:
Operación 1: eliminar el elemento en el índice 2 , es decir, arr[2] = 11 y reemplácelo con 11 números de 1 en él. Ahora la array arr[] se modifica a {2, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}.
Operación 2: Retire el elemento en el índice 1, es decir, arr[1] = 4 y reemplácelo con 4 números de 1 en él. Ahora la array arr[] se modifica a {2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}.Después de realizar las operaciones anteriores, el valor máximo de la array es 2, que es el valor mínimo posible.
Entrada: arr[]= {9}, K = 2
Salida: 1
Enfoque: El problema dado se puede resolver utilizando el hecho de que cada número se puede expresar como la suma de 1 , que es una potencia de 2 . Siga los pasos a continuación para resolver el problema:
- Ordene la array arr[] en orden descendente .
- Encuentre el conteo de 0s en la array arr[] , si el valor de conteo es N , luego imprima 0 como el valor máximo mínimo resultante de la array
- De lo contrario, si el valor de K es al menos N , imprima 1 como el valor máximo mínimo resultante de la array
- De lo contrario, imprima el valor de arr[K] como el valor máximo mínimo resultante de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum value
// of the maximum element of the array
// by splitting at most K array element
// into perfect powers of 2
void minimumSize(int arr[], int N, int K)
{
// Sort the array element in
// the ascending order
sort(arr, arr + N);
// Reverse the array
reverse(arr, arr + N);
// If count of 0 is equal to N
if (count(arr, arr + N, 0) == N)
cout << 0;
// Otherwise, if K is greater
// than or equal to N
else if (K >= N)
cout << 1 << endl;
// Otherwise
else
cout << arr[K] << endl;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 8, 2 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
minimumSize(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the minimum value
// of the maximum element of the array
// by splitting at most K array element
// into perfect powers of 2
static void minimumSize(int arr[], int N, int K)
{
// Sort the array element in
// the ascending order
Arrays.sort(arr);
// Reverse the array
reverse(arr);
// If count of 0 is equal to N
if (count(arr, 0) == N)
System.out.println(0);
// Otherwise, if K is greater
// than or equal to N
else if (K >= N)
System.out.println(1);
// Otherwise
else
System.out.println(arr[K]);
}
static void reverse(int[] a)
{
int i, k, t;
int n = a.length;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
static int count(int[] a, int n)
{
int freq = 0;
for(int i = 0; i < a.length; i++)
{
if (a[i] == n)
freq++;
}
return freq;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 4, 8, 2 };
int K = 2;
int N = arr.length;
minimumSize(arr, N, K);
}
}
// This code is contributed by offbeat
Python
# Python program for the above approach # Function to find the minimum value # of the maximum element of the array # by splitting at most K array element # into perfect powers of 2 def minimumSize(arr, N, K): # Sort the array element in # the ascending order arr.sort() # Reverse the array arr.reverse() # If count of 0 is equal to N zero = arr.count(0) if zero == N: print(0) # Otherwise, if K is greater # than or equal to N elif K >= N: print(1) # Otherwise else: print(arr[K]) # Driver Code arr = [2, 4, 8, 2] K = 2 N = len(arr) minimumSize(arr, N, K) # This code is contributed by sudhanshugupta2019a.
C#
// C#program for the above approach
using System;
class GFG
{
// Function to find the minimum value
// of the maximum element of the array
// by splitting at most K array element
// into perfect powers of 2
static void minimumSize(int[] arr, int N, int K)
{
// Sort the array element in
// the ascending order
Array.Sort(arr);
// Reverse the array
Array.Reverse(arr);
// If count of 0 is equal to N
if (count(arr, 0) == N)
Console.WriteLine(0);
// Otherwise, if K is greater
// than or equal to N
else if (K >= N)
Console.WriteLine(1);
// Otherwise
else
Console.WriteLine(arr[K]);
}
static void reverse(int[] a)
{
int i, t;
int n = a.Length;
for (i = 0; i < n / 2; i++) {
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
static int count(int[] a, int n)
{
int freq = 0;
for (int i = 0; i < a.Length; i++) {
if (a[i] == n)
freq++;
}
return freq;
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 2, 4, 8, 2 };
int K = 2;
int N = arr.Length;
minimumSize(arr, N, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum value
// of the maximum element of the array
// by splitting at most K array element
// into perfect powers of 2
function minimumSize(arr,N,K)
{
// Sort the array element in
// the ascending order
(arr).sort(function(a,b){return a-b;});
// Reverse the array
reverse(arr);
// If count of 0 is equal to N
if (count(arr, 0) == N)
document.write(0);
// Otherwise, if K is greater
// than or equal to N
else if (K >= N)
document.write(1);
// Otherwise
else
document.write(arr[K]);
}
function reverse(a)
{
let i, k, t;
let n = a.length;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
function count(a,n)
{
let freq = 0;
for(let i = 0; i < a.length; i++)
{
if (a[i] == n)
freq++;
}
return freq;
}
// Driver code
let arr=[2, 4, 8, 2];
let K = 2;
let N = arr.length;
minimumSize(arr, N, K);
// This code is contributed by avanitrachhadiya2155
</script>
2
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Otro enfoque eficiente: en el enfoque anterior, estamos ordenando la array y encontramos el (K+1)-ésimo elemento máximo para K<N. En lugar de ordenar la array, podemos usar una cola de prioridad para encontrar el elemento máximo (K+1) .
La complejidad temporal para este enfoque en el peor de los casos es O(N*log(K)) para k<N; de lo contrario, la complejidad temporal es O(1). Por lo tanto, el enfoque dado es mucho mejor que el enfoque anterior para un valor menor de k.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum value
// of the maximum element of the array
// by splitting at most K array element
// into perfect powers of 2
void minimumSize(int arr[], int N, int K)
{
// If count of 0 is equal to N
if (count(arr, arr + N, 0) == N)
cout << 0;
// Otherwise, if K is greater
// than or equal to N
else if (K >= N)
cout << 1 << endl;
// Otherwise
else
{
// Finding (K+1)th maximum element
// using a priority_queue
priority_queue<int, vector<int>, greater<int> >pq;
for (int i = 0; i < N; ++i) {
// Insert elements into
// the priority queue
pq.push(arr[i]);
// If size of the priority
// queue exceeds k+1
if (pq.size() > (K+1)) {
pq.pop();
}
}
// Print the (K+1)th maximum element
cout<<pq.top()<<endl;
}
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 8, 2 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
minimumSize(arr, N, K);
return 0;
}
// This code is contributed by Pushpesh raj
2
Complejidad de tiempo: O(N*log(K))
Espacio auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por shailjapriya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA