Horje
Maximum frequency of any array element possible by exactly K increments

Given an array arr[] consisting of N positive integers and an integer K, the task is to find the highest frequency of any array element after performing exactly K increments.

Examples:

Input: arr[] = {1, 3, 2, 2}, K = 2
Output: 3
Explanation:
Below are the operations performed:

  1. Add 1 to the element at index 2(= 2), then the array modifies to {1, 3, 3, 2}.
  2. Add 1 to the element at index 3(= 2), then the array modifies to {1, 3, 3, 3}.

After the above steps, the maximum frequency of an array element is 3.

Input: arr[] = {4, 3, 4}, K = 5
Output: 2

Approach: The given problem can be solved by using the Sliding Window Technique and Sorting. Follow the steps below to solve this problem:

  • Initialize the variables say start, end, sum as 0, and mostFreq as INT_MIN.
  • Sort the array arr[] in increasing order.
  • Iterate over the range [0, N – 1] using the variable end and perform the following steps:
    • Increment the value of sum by the value arr[end].
    • While the value of (sum + K) is less than the value of (arr[end] * (end – start+ 1)), then decrement the value of the sum by arr[start] and increment the value of start by 1.
    • Update the value of mostFreq to the maximum of mostFreq and (end – start + 1).
  • Initialize a variable, say reqSum as the value of (arr[N-1] * N – sum) that stores the resultant sum to make all the array elements equal.
  • If the value of mostFreq is N and the value of K is greater than reqSum, then decrement the value of K by reqSum.
  • If the value of K is a multiple of N, then print N. Otherwise, print the value of (N – 1).
  • After completing the above steps, print the value of mostFreq as the result.

Below is the implementation of the above approach:

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

Output: 

2

 

Time Complexity: O(N * log N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Find elements larger than half of the elements in an array | Set 2 Find elements larger than half of the elements in an array | Set 2
Generate a permutation of first N natural numbers from an array of differences between adjacent elements Generate a permutation of first N natural numbers from an array of differences between adjacent elements
Maximum element present in the array after performing queries to add K to range of indices [L, R] Maximum element present in the array after performing queries to add K to range of indices [L, R]
Minimize sum of numbers required to convert an array into a permutation of first N natural numbers Minimize sum of numbers required to convert an array into a permutation of first N natural numbers
Probability of obtaining pairs from two arrays such that element from the first array is smaller than that of the second array Probability of obtaining pairs from two arrays such that element from the first array is smaller than that of the second array

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 8



 

Horje