Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar la frecuencia máxima posible de cualquier elemento de la array en incrementos de K como máximo.
Ejemplos:
Entrada: arr[] = {1, 4, 8, 13}, N = 4, K = 5
Salida: 2
Explicación:
Incrementar arr[0] dos veces modifica arr[] a {4, 4, 8, 13}. Frecuencia máxima = 2.
Incrementar arr[1] cuatro veces modifica arr[] a {1, 8, 8, 13}. Frecuencia máxima = 2.
Incrementar arr[2] cinco veces modifica arr[] a {1, 4, 13, 13}. Frecuencia máxima = 2.
Por lo tanto, la frecuencia máxima posible de cualquier elemento de array que se puede obtener con un máximo de 5 incrementos es 2.Entrada: arr[] = {2, 4, 5}, N = 3, K = 4
Salida: 3
Enfoque: este problema se puede resolver utilizando la técnica de la ventana deslizante y la clasificación . Siga los pasos para resolver este problema.
- Ordene la array arr[] .
- Inicialice las variables sum = 0, start = 0 y la frecuencia resultante res = 0 .
- Recorra la array sobre el rango de índices [0, N – 1] y realice los siguientes pasos:
- Incrementa la suma por arr[end] .
- Iterar un bucle hasta que el valor de [(end – start + 1) * arr[end] – sum] sea menor que K y realizar las siguientes operaciones:
- Disminuye el valor de sum por arr[start] .
- Incremente el valor de inicio en 1 .
- Después de completar los pasos anteriores, todos los elementos sobre el rango [inicio, fin] pueden igualarse usando como máximo K operaciones. Por lo tanto, actualice el valor de res como el máximo de res y (fin – inicio + 1).
- Finalmente, imprima el valor de res como frecuencia del elemento más frecuente después de realizar K operaciones.
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 maximum possible
// frequency of a most frequent element
// after at most K increment operations
void maxFrequency(int arr[], int N, int K)
{
// Sort the input array
sort(arr, arr + N);
int start = 0, end = 0;
// Stores the sum of sliding
// window and the maximum possible
// frequency of any array element
int sum = 0, res = 0;
// Traverse the array
for (end = 0; end < N; end++) {
// Add the current element
// to the window
sum += arr[end];
// Decrease the window size
// If it is not possible to make the
// array elements in the window equal
while ((end - start + 1) * arr[end] - sum > K) {
// Update the value of sum
sum -= arr[start];
// Increment the value of start
start++;
}
// Update the maximum possible frequency
res = max(res, end - start + 1);
}
// Print the frequency of
// the most frequent array
// element after K increments
cout << res << endl;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 8, 13 };
int N = 4;
int K = 5;
maxFrequency(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// Function to find the maximum possible
// frequency of a most frequent element
// after at most K increment operations
static void maxFrequency(int arr[], int N, int K)
{
// Sort the input array
Arrays.sort(arr);
int start = 0, end = 0;
// Stores the sum of sliding
// window and the maximum possible
// frequency of any array element
int sum = 0, res = 0;
// Traverse the array
for(end = 0; end < N; end++)
{
// Add the current element
// to the window
sum += arr[end];
// Decrease the window size
// If it is not possible to make the
// array elements in the window equal
while ((end - start + 1) *
arr[end] - sum > K)
{
// Update the value of sum
sum -= arr[start];
// Increment the value of start
start++;
}
// Update the maximum possible frequency
res = Math.max(res, end - start + 1);
}
// Print the frequency of
// the most frequent array
// element after K increments
System.out.println(res);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 4, 8, 13 };
int N = 4;
int K = 5;
maxFrequency(arr, N, K);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to find the maximum possible # frequency of a most frequent element # after at most K increment operations def maxFrequency(arr, N, K): # Sort the input array arr.sort() start = 0 end = 0 # Stores the sum of sliding # window and the maximum possible # frequency of any array element sum = 0 res = 0 # Traverse the array for end in range(N): # Add the current element # to the window sum += arr[end] # Decrease the window size # If it is not possible to make the # array elements in the window equal while ((end - start + 1) * arr[end] - sum > K): # Update the value of sum sum -= arr[start] # Increment the value of start start += 1 # Update the maximum possible frequency res = max(res, end - start + 1) # Print the frequency of # the most frequent array # element after K increments print(res) # Driver code if __name__ == '__main__': arr = [ 1, 4, 8, 13 ] N = 4 K = 5 maxFrequency(arr, N, K) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum possible
// frequency of a most frequent element
// after at most K increment operations
static void maxFrequency(int[] arr, int N, int K)
{
// Sort the input array
Array.Sort(arr);
int start = 0, end = 0;
// Stores the sum of sliding
// window and the maximum possible
// frequency of any array element
int sum = 0, res = 0;
// Traverse the array
for(end = 0; end < N; end++)
{
// Add the current element
// to the window
sum += arr[end];
// Decrease the window size
// If it is not possible to make the
// array elements in the window equal
while ((end - start + 1) *
arr[end] - sum > K)
{
// Update the value of sum
sum -= arr[start];
// Increment the value of start
start++;
}
// Update the maximum possible frequency
res = Math.Max(res, end - start + 1);
}
// Print the frequency of
// the most frequent array
// element after K increments
Console.WriteLine(res);
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 4, 8, 13 };
int N = 4;
int K = 5;
maxFrequency(arr, N, K);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum possible
// frequency of a most frequent element
// after at most K increment operations
function maxFrequency(arr, N, K) {
// Sort the input array
arr.sort((a, b) => a - b);
let start = 0, end = 0;
// Stores the sum of sliding
// window and the maximum possible
// frequency of any array element
let sum = 0, res = 0;
// Traverse the array
for (end = 0; end < N; end++) {
// Add the current element
// to the window
sum += arr[end];
// Decrease the window size
// If it is not possible to make the
// array elements in the window equal
while ((end - start + 1) * arr[end] - sum > K) {
// Update the value of sum
sum -= arr[start];
// Increment the value of start
start++;
}
// Update the maximum possible frequency
res = Math.max(res, end - start + 1);
}
// Print the frequency of
// the most frequent array
// element after K increments
document.write(res + "<br>");
}
// Driver code
let arr = [1, 4, 8, 13];
let N = 4;
let K = 5;
maxFrequency(arr, N, K);
</script>
Producción:
2
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por srinivasteja18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA