Dada una array y un valor k. Tenemos que encontrar el número máximo de elementos iguales posibles para la array para que podamos aumentar los elementos de la array incrementando un total de k como máximo.
Ejemplos:
Entrada: array = { 2, 4, 9 }, k = 3
Salida: 2
Se nos permite hacer como máximo tres incrementos. Podemos hacer dos elementos 4 aumentando 2 en 2. Tenga en cuenta que no podemos hacer dos elementos 9 ya que convertir 4 a 9 requiere 5 incrementos.
Entrada: array = { 5, 5, 3, 1 }, k = 5
Salida: 3
Explicación: Aquí el 1.° y el 2.° elemento son iguales. Entonces podemos aumentar el tercer elemento 3 hasta 5. Entonces k se convierte en (k-2) = 3. Ahora no podemos aumentar de 1 a 5 porque el valor de k es 3 y necesitamos 4 para la actualización. Por lo tanto, los elementos iguales posibles son 3. Aquí también podemos aumentar 1 a 5. Entonces también tenemos 3 porque no podemos actualizar 3 a 5.
Entrada: array = {5, 5, 3, 1}, k = 6
Salida: 4
Enfoque ingenuo: en el enfoque ingenuo tenemos un algoritmo en tiempo O (n ^ 2) en el que verificamos para cada elemento cuántos otros elementos se pueden incrementar para que sean iguales a ellos.
Enfoque eficiente: en este enfoque, primero ordenaremos la array. Entonces mantenemos dos arreglos. La primera es la array de suma de prefijos que almacena la suma de prefijos de la array y otra es la array maxx[] que almacena el elemento máximo encontrado hasta cada punto, es decir, max[i] significa el elemento máximo de 1 a i. Después de almacenar estos valores en la array de prefijos [] y la array maxx [], hacemos la búsqueda binaria de 1 a n (número de elementos de la array) para calcular cuántos elementos se pueden incrementar para hacerlos iguales. En la búsqueda binaria, usamos una función en la que determinamos¿Cuál es el número de elementos que se pueden incrementar para hacerlos iguales a un solo valor ?
C++
// C++ program to find maximum elements that can
// be made equal with k updates
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the maximum number of
// equal elements possible with atmost K increment
// of values .Here we have done sliding window
// to determine that whether there are x number of
// elements present which on increment will become
// equal. The loop here will run in fashion like
// 0...x-1, 1...x, 2...x+1, ...., n-x-1...n-1
bool ElementsCalculationFunc(int pre[], int maxx[],
int x, int k, int n)
{
for (int i = 0, j = x; j <= n; j++, i++) {
// It can be explained with the reasoning
// that if for some x number of elements
// we can update the values then the
// increment to the segment (i to j having
// length -> x) so that all will be equal is
// (x*maxx[j]) this is the total sum of
// segment and (pre[j]-pre[i]) is present sum
// So difference of them should be less than k
// if yes, then that segment length(x) can be
// possible return true
if (x * maxx[j] - (pre[j] - pre[i]) <= k)
return true;
}
return false;
}
void MaxNumberOfElements(int a[], int n, int k)
{
// sort the array in ascending order
sort(a, a + n);
int pre[n + 1]; // prefix sum array
int maxx[n + 1]; // maximum value array
// Initializing the prefix array
// and maximum array
for (int i = 0; i <= n; ++i) {
pre[i] = 0;
maxx[i] = 0;
}
for (int i = 1; i <= n; i++) {
// Calculating prefix sum of the array
pre[i] = pre[i - 1] + a[i - 1];
// Calculating max value upto that position
// in the array
maxx[i] = max(maxx[i - 1], a[i - 1]);
}
// Binary search applied for
// computation here
int l = 1, r = n, ans;
while (l < r) {
int mid = (l + r) / 2;
if (ElementsCalculationFunc(pre, maxx,
mid - 1, k, n)) {
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
// printing result
cout << ans << "\n";
}
int main()
{
int arr[] = { 2, 4, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
MaxNumberOfElements(arr, n, k);
return 0;
}
Java
// java program to find maximum elements that can
// be made equal with k updates
import java.util.Arrays;
public class GFG {
// Function to calculate the maximum number of
// equal elements possible with atmost K increment
// of values .Here we have done sliding window
// to determine that whether there are x number of
// elements present which on increment will become
// equal. The loop here will run in fashion like
// 0...x-1, 1...x, 2...x+1, ...., n-x-1...n-1
static boolean ElementsCalculationFunc(int pre[],
int maxx[], int x, int k, int n)
{
for (int i = 0, j = x; j <= n; j++, i++) {
// It can be explained with the reasoning
// that if for some x number of elements
// we can update the values then the
// increment to the segment (i to j having
// length -> x) so that all will be equal is
// (x*maxx[j]) this is the total sum of
// segment and (pre[j]-pre[i]) is present sum
// So difference of them should be less than k
// if yes, then that segment length(x) can be
// possible return true
if (x * maxx[j] - (pre[j] - pre[i]) <= k)
return true;
}
return false;
}
static void MaxNumberOfElements(int a[], int n, int k)
{
// sort the array in ascending order
Arrays.sort(a);
int []pre = new int[n + 1]; // prefix sum array
int []maxx = new int[n + 1]; // maximum value array
// Initializing the prefix array
// and maximum array
for (int i = 0; i <= n; ++i) {
pre[i] = 0;
maxx[i] = 0;
}
for (int i = 1; i <= n; i++) {
// Calculating prefix sum of the array
pre[i] = pre[i - 1] + a[i - 1];
// Calculating max value upto that position
// in the array
maxx[i] = Math.max(maxx[i - 1], a[i - 1]);
}
// Binary search applied for
// computation here
int l = 1, r = n, ans=0;
while (l < r) {
int mid = (l + r) / 2;
if (ElementsCalculationFunc(pre, maxx,
mid - 1, k, n))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
// printing result
System.out.print((int)ans + "\n");
}
public static void main(String args[]) {
int arr[] = { 2, 4, 9 };
int n = arr.length;
int k = 3;
MaxNumberOfElements(arr, n, k);
}
}
// This code is contributed by Sam007
Python3
# Python3 program to find maximum elements # that can be made equal with k updates # Function to calculate the maximum number of # equal elements possible with atmost K increment # of values .Here we have done sliding window # to determine that whether there are x number of # elements present which on increment will become # equal. The loop here will run in fashion like # 0...x-1, 1...x, 2...x+1, ...., n-x-1...n-1 def ElementsCalculationFunc(pre, maxx, x, k, n): i = 0 j = x while j <= n: # It can be explained with the reasoning # that if for some x number of elements # we can update the values then the # increment to the segment (i to j having # length -> x) so that all will be equal is # (x*maxx[j]) this is the total sum of # segment and (pre[j]-pre[i]) is present sum # So difference of them should be less than k # if yes, then that segment length(x) can be # possible return true if (x * maxx[j] - (pre[j] - pre[i]) <= k): return True i += 1 j += 1 return False def MaxNumberOfElements( a, n, k): # sort the array in ascending order a.sort() pre = [0] * (n + 1) # prefix sum array maxx = [0] * (n + 1) # maximum value array # Initializing the prefix array # and maximum array for i in range (n + 1): pre[i] = 0 maxx[i] = 0 for i in range(1, n+1): # Calculating prefix sum of the array pre[i] = pre[i - 1] + a[i - 1] # Calculating max value upto that # position in the array maxx[i] = max(maxx[i - 1], a[i - 1]) # Binary search applied for # computation here l = 1 r = n while (l < r) : mid = (l + r) // 2 if (ElementsCalculationFunc(pre, maxx, mid - 1, k, n)): ans = mid l = mid + 1 else: r = mid - 1 # printing result print (ans) # Driver Code if __name__ == "__main__": arr = [2, 4, 9 ] n = len(arr) k = 3 MaxNumberOfElements(arr, n, k) # This code is contributed by Ita_c
C#
// C# program to find maximum elements that can
// be made equal with k updates
using System;
class GFG {
// Function to calculate the maximum number of
// equal elements possible with atmost K increment
// of values .Here we have done sliding window
// to determine that whether there are x number of
// elements present which on increment will become
// equal. The loop here will run in fashion like
// 0...x-1, 1...x, 2...x+1, ...., n-x-1...n-1
static bool ElementsCalculationFunc(int []pre,
int []maxx, int x, int k, int n)
{
for (int i = 0, j = x; j <= n; j++, i++) {
// It can be explained with the reasoning
// that if for some x number of elements
// we can update the values then the
// increment to the segment (i to j having
// length -> x) so that all will be equal is
// (x*maxx[j]) this is the total sum of
// segment and (pre[j]-pre[i]) is present sum
// So difference of them should be less than k
// if yes, then that segment length(x) can be
// possible return true
if (x * maxx[j] - (pre[j] - pre[i]) <= k)
return true;
}
return false;
}
static void MaxNumberOfElements(int []a, int n, int k)
{
// sort the array in ascending order
Array.Sort(a);
int []pre = new int[n + 1]; // prefix sum array
int []maxx = new int[n + 1]; // maximum value array
// Initializing the prefix array
// and maximum array
for (int i = 0; i <= n; ++i) {
pre[i] = 0;
maxx[i] = 0;
}
for (int i = 1; i <= n; i++) {
// Calculating prefix sum of the array
pre[i] = pre[i - 1] + a[i - 1];
// Calculating max value upto that position
// in the array
maxx[i] = Math.Max(maxx[i - 1], a[i - 1]);
}
// Binary search applied for
// computation here
int l = 1, r = n, ans=0;
while (l < r) {
int mid = (l + r) / 2;
if (ElementsCalculationFunc(pre, maxx,
mid - 1, k, n))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
// printing result
Console.Write ((int)ans + "\n");
}
// Driver code
public static void Main()
{
int []arr = { 2, 4, 9 };
int n = arr.Length;
int k = 3;
MaxNumberOfElements(arr, n, k);
}
}
// This code is contributed by Sam007
PHP
<?php
//PHP program to find maximum elements that can
// be made equal with k updates
// Function to calculate the maximum number of
// equal elements possible with atmost K increment
// of values .Here we have done sliding window
// to determine that whether there are x number of
// elements present which on increment will become
// equal. The loop here will run in fashion like
// 0...x-1, 1...x, 2...x+1, ...., n-x-1...n-1
function ElementsCalculationFunc($pre, $maxx,$x, $k, $n)
{
for ( $i = 0, $j = $x; $j <= $n; $j++, $i++) {
// It can be explained with the reasoning
// that if for some x number of elements
// we can update the values then the
// increment to the segment (i to j having
// length -> x) so that all will be equal is
// (x*maxx[j]) this is the total sum of
// segment and (pre[j]-pre[i]) is present sum
// So difference of them should be less than k
// if yes, then that segment length(x) can be
// possible return true
if ($x * $maxx[$j] - ($pre[$j] - $pre[$i]) <= $k)
return true;
}
return false;
}
function MaxNumberOfElements($a, $n, $k)
{
// sort the array in ascending order
sort($a);
$pre[$n + 1]=array(); // prefix sum array
$maxx[$n + 1]=array(); // maximum value array
// Initializing the prefix array
// and maximum array
for ($i = 0; $i <= $n; ++$i) {
$pre[$i] = 0;
$maxx[$i] = 0;
}
for ($i = 1; $i <= $n; $i++) {
// Calculating prefix sum of the array
$pre[$i] = $pre[$i - 1] + $a[$i - 1];
// Calculating max value upto that position
// in the array
$maxx[$i] = max($maxx[$i - 1], $a[$i - 1]);
}
// Binary search applied for
// computation here
$l = 1;
$r = $n;
$ans;
while ($l < $r) {
$mid = ($l + $r) / 2;
if (ElementsCalculationFunc($pre, $maxx,
$mid - 1, $k, $n)) {
$ans = $mid;
$l = $mid + 1;
}
else
$r = $mid - 1;
}
// printing result
echo $ans , "\n";
}
//Code driven
$arr = array(2, 4, 9 );
$n = sizeof($arr) / sizeof($arr[0]);
$k = 3;
MaxNumberOfElements($arr, $n, $k);
#This code is contributed by akt_mit.
?>
Javascript
<script>
// javascript program to find maximum elements that can
// be made equal with k updates
// Function to calculate the maximum number of
// equal elements possible with atmost K increment
// of values .Here we have done sliding window
// to determine that whether there are x number of
// elements present which on increment will become
// equal. The loop here will run in fashion like
// 0...x-1, 1...x, 2...x+1, ...., n-x-1...n-1
function ElementsCalculationFunc(pre, maxx, x, k, n)
{
for (let i = 0, j = x; j <= n; j++, i++)
{
// It can be explained with the reasoning
// that if for some x number of elements
// we can update the values then the
// increment to the segment (i to j having
// length -> x) so that all will be equal is
// (x*maxx[j]) this is the total sum of
// segment and (pre[j]-pre[i]) is present sum
// So difference of them should be less than k
// if yes, then that segment length(x) can be
// possible return true
if (x * maxx[j] - (pre[j] - pre[i]) <= k)
return true;
}
return false;
}
function MaxNumberOfElements(a, n, k)
{
// sort the array in ascending order
a.sort(function(a,b){return a-b;});
let pre = new Array(n + 1); // prefix sum array
let maxx = new Array(n + 1); // maximum value array
// Initializing the prefix array
// and maximum array
for (let i = 0; i <= n; ++i)
{
pre[i] = 0;
maxx[i] = 0;
}
for (let i = 1; i <= n; i++)
{
// Calculating prefix sum of the array
pre[i] = pre[i - 1] + a[i - 1];
// Calculating max value upto that position
// in the array
maxx[i] = Math.max(maxx[i - 1], a[i - 1]);
}
// Binary search applied for
// computation here
let l = 1, r = n, ans=0;
while (l < r)
{
let mid = Math.floor((l + r) / 2);
if (ElementsCalculationFunc(pre, maxx,
mid - 1, k, n))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
// printing result
document.write(ans + "\n");
}
let arr = [2, 4, 9 ];
let n = arr.length;
let k = 3;
MaxNumberOfElements(arr, n, k);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad de tiempo: O(nlog(n))
Complejidad de espacio: O(n)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA