Dada una array arr[] que consta de N enteros positivos y un entero K , la tarea es encontrar la frecuencia más alta de cualquier elemento de la array después de realizar exactamente K incrementos.
Ejemplos:
Entrada: arr[] = {1, 3, 2, 2}, K = 2
Salida: 3
Explicación:
A continuación se muestran las operaciones realizadas:
- Agregue 1 al elemento en el índice 2 (= 2), luego la array se modifica a {1, 3, 3, 2}.
- Agregue 1 al elemento en el índice 3 (= 2), luego la array se modifica a {1, 3, 3, 3}.
Después de los pasos anteriores, la frecuencia máxima de un elemento de array es 3.
Entrada: arr[] = {4, 3, 4}, K = 5
Salida: 2
Enfoque: El problema dado se puede resolver utilizando la técnica de la ventana deslizante y la clasificación . Siga los pasos a continuación para resolver este problema:
- Inicialice las variables, digamos start , end , sum as 0 y mostFreq como INT_MIN.
- Ordene la array arr[] en orden creciente .
- Iterar sobre el rango [0, N – 1] usando la variable end y realizar los siguientes pasos:
- Incrementa el valor de sum por el valor arr[end] .
- Mientras que el valor de (sum + K) es menor que el valor de (arr[end] * (end – start+ 1)) , luego disminuya el valor de la suma en arr[start] e incremente el valor de start en 1 .
- Actualice el valor de mostFreq al máximo de mostFreq y (end – start + 1) .
- Inicialice una variable, digamos reqSum como el valor de (arr[N-1] * N – sum) que almacena la suma resultante para hacer que todos los elementos de la array sean iguales .
- Si el valor de mostFreq es N y el valor de K es mayor que reqSum , disminuya el valor de K en reqSum .
- Si el valor de K es un múltiplo de N , imprima N. De lo contrario, imprima el valor de (N – 1) .
- Después de completar los pasos anteriores, imprima el valor de mostFreq como resultado.
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 highest frequency
// of any array element possible by
// exactly K increment operations
void findMostFrequent(int arr[], int N,
int K)
{
int start = 0, end = 0;
// Sort the given array
sort(arr, arr + N);
// Stores the maximum frequency
// and the sum of sliding window
int mostFreq = INT_MIN, sum = 0;
// Traverse the array arr[]
for (end = 0; end < N; end++) {
// Add the current element
// to the window
sum = sum + arr[end];
// Decreasing the window size
while (sum + K < arr[end] * (end - start + 1)) {
// Update the value of sum
// by subtracting arr[start]
sum = sum - arr[start];
// Increment the value
// of the start
start++;
}
// Update maximum window size
mostFreq = max(mostFreq,
end - start + 1);
}
// Stores the required sum to
// make all elements of arr[] equal
int reqSum = arr[N - 1] * N - sum;
// If result from at most K increments
// is N and K is greater than reqSum
if (mostFreq == N && reqSum < K) {
// Decrement the value of K
// by reqSum
K = K - reqSum;
// If K is mutilpe of N then
// increment K/N times to
// every element
if (K % N == 0) {
cout << N << endl;
}
// Otherwise first make every
// element equal then increment
// remaining K to one element
else {
cout << N - 1 << endl;
}
return;
}
// Print the answer
cout << mostFreq << endl;
}
// Driver Code
int main()
{
int arr[] = { 4, 3, 4 };
int K = 5;
int N = sizeof(arr) / sizeof(arr[0]);
findMostFrequent(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the highest frequency
// of any array element possible by
// exactly K increment operations
static void findMostFrequent(int arr[], int N,
int K)
{
int start = 0, end = 0;
// Sort the given array
Arrays.sort(arr);
// Stores the maximum frequency
// and the sum of sliding window
int mostFreq = Integer.MIN_VALUE, sum = 0;
// Traverse the array arr[]
for (end = 0; end < N; end++) {
// Add the current element
// to the window
sum = sum + arr[end];
// Decreasing the window size
while (sum + K < arr[end] * (end - start + 1)) {
// Update the value of sum
// by subtracting arr[start]
sum = sum - arr[start];
// Increment the value
// of the start
start++;
}
// Update maximum window size
mostFreq = Math.max(mostFreq,
end - start + 1);
}
// Stores the required sum to
// make all elements of arr[] equal
int reqSum = arr[N - 1] * N - sum;
// If result from at most K increments
// is N and K is greater than reqSum
if (mostFreq == N && reqSum < K) {
// Decrement the value of K
// by reqSum
K = K - reqSum;
// If K is mutilpe of N then
// increment K/N times to
// every element
if (K % N == 0) {
System.out.println(N);
}
// Otherwise first make every
// element equal then increment
// remaining K to one element
else {
System.out.println(N - 1);
}
return;
}
// Print the answer
System.out.println( mostFreq);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 3, 4 };
int K = 5;
int N = arr.length;
findMostFrequent(arr, N, K);
}
}
// This code is contributed by target_2.
Python3
# Python program for the above approach # Function to find the highest frequency # of any array element possible by # exactly K increment operations def findMostFrequent( arr, N, K): start = 0 end = 0 # Sort the given array arr.sort() # Stores the maximum frequency # and the sum of sliding window mostFreq = -2**31 sum = 0 # Traverse the array arr[] for end in range(N): # Add the current element # to the window sum = sum + arr[end] # Decreasing the window size while (sum + K < arr[end] * (end - start + 1)): # Update the value of sum # by subtracting arr[start] sum = sum - arr[start] # Increment the value # of the start start += 1 # Update maximum window size mostFreq = max(mostFreq, end - start + 1) # Stores the required sum to # make all elements of arr[] equal reqSum = arr[N - 1] * N - sum # If result from at most K increments # is N and K is greater than reqSum if (mostFreq == N and reqSum < K): # Decrement the value of K # by reqSum K = K - reqSum # If K is mutilpe of N then # increment K/N times to # every element if (K % N == 0): print(N) # Otherwise first make every # element equal then increment # remaining K to one element else: print(N - 1) return # Print the answer print(mostFreq) # Driver Code arr = [4, 3, 4] K = 5 N = len(arr) findMostFrequent(arr, N, K) # This code is contributed by shubhamsingh10
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the highest frequency
// of any array element possible by
// exactly K increment operations
static void findMostFrequent(int []arr, int N,
int K)
{
int start = 0, end = 0;
// Sort the given array
Array.Sort(arr);
// Stores the maximum frequency
// and the sum of sliding window
int mostFreq = Int32.MinValue, sum = 0;
// Traverse the array arr[]
for(end = 0; end < N; end++)
{
// Add the current element
// to the window
sum = sum + arr[end];
// Decreasing the window size
while (sum + K < arr[end] * (end - start + 1))
{
// Update the value of sum
// by subtracting arr[start]
sum = sum - arr[start];
// Increment the value
// of the start
start++;
}
// Update maximum window size
mostFreq = Math.Max(mostFreq,
end - start + 1);
}
// Stores the required sum to
// make all elements of arr[] equal
int reqSum = arr[N - 1] * N - sum;
// If result from at most K increments
// is N and K is greater than reqSum
if (mostFreq == N && reqSum < K)
{
// Decrement the value of K
// by reqSum
K = K - reqSum;
// If K is mutilpe of N then
// increment K/N times to
// every element
if (K % N == 0)
{
Console.Write(N);
}
// Otherwise first make every
// element equal then increment
// remaining K to one element
else
{
Console.Write(N - 1);
}
return;
}
// Print the answer
Console.Write( mostFreq);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 4, 3, 4 };
int K = 5;
int N = arr.Length;
findMostFrequent(arr, N, K);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program for the above approach
// Function to find the highest frequency
// of any array element possible by
// exactly K increment operations
function findMostFrequent(arr, N, K) {
let start = 0, end = 0;
// Sort the given array
arr.sort((a, b) => a - b);
// Stores the maximum frequency
// and the sum of sliding window
let mostFreq = Number.MIN_SAFE_INTEGER, sum = 0;
// Traverse the array arr[]
for (end = 0; end < N; end++) {
// Add the current element
// to the window
sum = sum + arr[end];
// Decreasing the window size
while (sum + K < arr[end] * (end - start + 1)) {
// Update the value of sum
// by subtracting arr[start]
sum = sum - arr[start];
// Increment the value
// of the start
start++;
}
// Update maximum window size
mostFreq = Math.max(mostFreq,
end - start + 1);
}
// Stores the required sum to
// make all elements of arr[] equal
let reqSum = arr[N - 1] * N - sum;
// If result from at most K increments
// is N and K is greater than reqSum
if (mostFreq == N && reqSum < K) {
// Decrement the value of K
// by reqSum
K = K - reqSum;
// If K is mutilpe of N then
// increment K/N times to
// every element
if (K % N == 0) {
document.write(N + "<br>");
}
// Otherwise first make every
// element equal then increment
// remaining K to one element
else {
document.write(N - 1 + "<br>");
}
return;
}
// Print the answer
document.write(mostFreq + "<br>");
}
// Driver Code
let arr = [4, 3, 4];
let K = 5;
let N = arr.length
findMostFrequent(arr, N, K);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
2
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA