Frecuencia máxima de cualquier elemento de array posible en incrementos de K como máximo

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++ 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 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 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# 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

<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>

2

Complejidad temporal: O(NlogN) 
Espacio auxiliar: O(1)