Maximum frequency of any array element possible by at most K increments
Given an array arr[] of size N and an integer K, the task is to find the maximum possible frequency of any array element by at most K increments.
Examples:
Input: arr[] = {1, 4, 8, 13}, N = 4, K = 5
Output: 2
Explanation:
Incrementing arr[0] twice modifies arr[] to {4, 4, 8, 13}. Maximum frequency = 2.
Incrementing arr[1] four times modifies arr[] to {1, 8, 8, 13}. Maximum frequency = 2.
Incrementing arr[2] five times modifies arr[] to {1, 4, 13, 13}. Maximum frequency = 2.
Therefore, the maximum possible frequency of any array element that can be obtained by at most 5 increments is 2.Input: arr[] = {2, 4, 5}, N = 3, K = 4
Output: 3
Approach: This problem can be solved by using Sliding Window Technique and Sorting. Follow the steps to solve this problem.
- Sort the array arr[].
- Initialize variables sum = 0, start = 0 and resultant frequency res = 0.
- Traverse the array over the range of indices [0, N – 1] and perform the following steps:
- Increment sum by arr[end].
- Iterate a loop until the value of [(end – start + 1) * arr[end] – sum] is less than K and perform the following operations:
- Decrement the value of sum by arr[start].
- Increment the value of start by 1.
- After completing the above steps, all the elements over the range [start, end] can be made equal by using at most K operations. Therefore, update the value of res as the maximum of res and (end – start + 1).
- Finally, print the value of res as frequency of most frequent element after performing Koperations.
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 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> |
2
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
Approach: Using Binary Search
- Sort the input array in ascending order.
- Calculate prefix sums of the input array and store them in a vector.
- For each index in the sorted array, find the maximum frequency of the element at that index, such that we can change any number of elements to that element with a cost not exceeding k.
- The maximum frequency for all indices is the answer.
To find the maximum frequency of the element at a particular index:
- Start with a range of [0, index].
- For each iteration, find the middle point of the range.
- Calculate the sum of the elements from the middle point to the index using the prefix sums.
- Calculate the cost of changing all elements from the middle point to the index to the element at the current index.
- If the cost is less than or equal to k, move the left boundary of the range to the middle point.
- If the cost is greater than k, move the right boundary of the range to the middle point.
- Repeat steps 2-6 until the range is reduced to a single point.
- The frequency of the element is the difference between the index and the left boundary of the range plus one.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Declare a vector to store prefix sum values vector< long long > preSum; // Define the helper function that takes in a vector of // integers nums, an integer k, and an integer index as // input int helper(vector< int >& nums, int k, int index) { // Initialize variables low, high, and res to store the // lower index, higher index, and the result index int low = 0; int high = index; int res = index; // Perform binary search to find the maximum frequency // of the current element by varying the element to its // left while (low <= high) { int mid = low + (high - low) / 2; // Calculate the sum of the elements from mid to // index long long s = preSum[index + 1] - preSum[mid]; // Check if the sum can be increased by at most k by // replacing the elements from mid to index with the // current element nums[index] if (s + k >= ( long long )(index - mid + 1) * nums[index]) { // If yes, update the result to mid and search // for a better solution to the left of mid res = mid; high = mid - 1; } else { // If no, search for a better solution to the // right of mid low = mid + 1; } } // Return the frequency of the current element return index - res + 1; } // Define the maxFrequency function that takes in a vector // of integers nums and an integer k as input int maxFrequency(vector< int >& nums, int k) { // Sort the input vector in non-decreasing order sort(nums.begin(), nums.end()); // Get the size of the input vector int n = nums.size(); // Resize the prefix sum vector to size n+1 preSum.resize(n + 1); // Calculate the prefix sum values and store them in the // prefix sum vector for ( int i = 0; i < n; i++) { preSum[i + 1] = preSum[i] + nums[i]; } // Initialize a variable ans to store the maximum // frequency int ans = 0; // Iterate over each element of the input vector for ( int i = 0; i < n; i++) { // Update the maximum frequency by taking the // maximum of the current maximum frequency and the // frequency of the current element ans = max(ans, helper(nums, k, i)); } // Return the maximum frequency return ans; } // Driver code int main() { vector< int > arr = { 1, 4, 8, 13 }; int K = 5; cout << "Frequency of the Most Frequent Element : " << maxFrequency(arr, K); return 0; } //this code is contributed by Ravi Singh |
Java
import java.util.*; public class Main { // Declare a list to store prefix sum values static List<Long> preSum = new ArrayList<>(); // Define the helper function that takes in a list of // integers nums, an integer k, and an integer index as // input static int helper(List<Integer> nums, int k, int index) { // Initialize variables low, high, and res to store // the lower index, higher index, and the result // index int low = 0 ; int high = index; int res = index; // Perform binary search to find the maximum // frequency of the current element by varying the // element to its left while (low <= high) { int mid = low + (high - low) / 2 ; // Calculate the sum of the elements from mid to // index long s = preSum.get(index + 1 ) - preSum.get(mid); // Check if the sum can be increased by at most // k by replacing the elements from mid to index // with the current element nums[index] if (s + k >= ( long )(index - mid + 1 ) * nums.get(index)) { // If yes, update the result to mid and // search for a better solution to the left // of mid res = mid; high = mid - 1 ; } else { // If no, search for a better solution to // the right of mid low = mid + 1 ; } } // Return the frequency of the current element return index - res + 1 ; } // Define the maxFrequency function that takes in a list // of integers nums and an integer k as input static int maxFrequency(List<Integer> nums, int k) { // Sort the input list in non-decreasing order Collections.sort(nums); // Get the size of the input list int n = nums.size(); // Resize the prefix sum list to size n+1 preSum = new ArrayList<>( Collections.nCopies(n + 1 , 0L)); // Calculate the prefix sum values and store them in // the prefix sum list for ( int i = 0 ; i < n; i++) { preSum.set(i + 1 , preSum.get(i) + nums.get(i)); } // Initialize a variable ans to store the maximum // frequency int ans = 0 ; // Iterate over each element of the input list for ( int i = 0 ; i < n; i++) { // Update the maximum frequency by taking the // maximum of the current maximum frequency and // the frequency of the current element ans = Math.max(ans, helper(nums, k, i)); } // Return the maximum frequency return ans; } // Driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList( 1 , 4 , 8 , 13 ); int K = 5 ; System.out.println( "Frequency of the Most Frequent Element : " + maxFrequency(arr, K)); } } //this code is contributed by Ravi Singh |
Python3
def helper(nums, k, index): # Initialize variables low, high, and res to store the # lower index, higher index, and the result index low = 0 high = index res = index # Perform binary search to find the maximum frequency # of the current element by varying the element to its # left while low < = high: mid = low + (high - low) / / 2 # Calculate the sum of the elements from mid to index s = sum (nums[mid:index + 1 ]) # Check if the sum can be increased by at most k by # replacing the elements from mid to index with the # current element nums[index] if s + k > = (index - mid + 1 ) * nums[index]: # If yes, update the result to mid and search # for a better solution to the left of mid res = mid high = mid - 1 else : # If no, search for a better solution to the # right of mid low = mid + 1 # Return the frequency of the current element return index - res + 1 def maxFrequency(nums, k): # Sort the input list in non-decreasing order nums.sort() # Get the size of the input list n = len (nums) # Initialize a variable ans to store the maximum frequency ans = 0 # Iterate over each element of the input list for i in range (n): # Update the maximum frequency by taking the # maximum of the current maximum frequency and the # frequency of the current element ans = max (ans, helper(nums, k, i)) # Return the maximum frequency return ans # Driver code if __name__ = = "__main__" : arr = [ 1 , 4 , 8 , 13 ] K = 5 print ( "Frequency of the Most Frequent Element:" , maxFrequency(arr, K)) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Declare a list to store prefix sum values static List< long > preSum = new List< long >(); // Define the helper function that takes a list of integers // nums, an integer k, and an integer index as input static int Helper(List< int > nums, int k, int index) { // Initialize variables low, high, and res to store the lower index, // higher index, and the result index int low = 0; int high = index; int res = index; // Perform binary search to find the maximum frequency of // the current element by varying the element to its left while (low <= high) { int mid = low + (high - low) / 2; // Calculate the sum of the elements from mid to index long s = preSum[index + 1] - preSum[mid]; // Check if the sum can be increased by at most k by // replacing the elements from mid to index with // the current element nums[index] if (s + k >= ( long )(index - mid + 1) * nums[index]) { // If yes, update the result to mid and search for a // better solution to the left of mid res = mid; high = mid - 1; } else { // If no, search for a better solution to the right of mid low = mid + 1; } } // Return the frequency of the current element return index - res + 1; } // Define the MaxFrequency function that takes a list of // integers nums and an integer k as input static int MaxFrequency(List< int > nums, int k) { // Sort the input list in non-decreasing order nums.Sort(); // Get the size of the input list int n = nums.Count; // Resize the prefix sum list to size n+1 preSum = new List< long >( new long [n + 1]); // Calculate the prefix sum values and store them in the prefix sum list for ( int i = 0; i < n; i++) { preSum[i + 1] = preSum[i] + nums[i]; } // Initialize a variable ans to store the maximum frequency int ans = 0; // Iterate over each element of the input list for ( int i = 0; i < n; i++) { // Update the maximum frequency by taking the maximum of // the current maximum frequency and the frequency of the current element ans = Math.Max(ans, Helper(nums, k, i)); } // Return the maximum frequency return ans; } // Driver code static void Main( string [] args) { List< int > arr = new List< int > { 1, 4, 8, 13 }; int K = 5; Console.WriteLine( "Frequency of the Most Frequent Element: " + MaxFrequency(arr, K)); } } |
Javascript
// Define the maxFrequency function that takes in an array of integers nums and an integer k as input function maxFrequency(nums, k) { // Sort the input array in non-decreasing order nums.sort((a, b) => a - b); // Get the length of the input array const n = nums.length; // Initialize a prefix sum array preSum with n+1 elements, all initialized to 0 const preSum = new Array(n + 1).fill(0); // Calculate the prefix sum values and store them in the prefix sum array for (let i = 0; i < n; i++) { preSum[i + 1] = preSum[i] + nums[i]; } // Define the helper function that takes an index as input function helper(index) { // Initialize variables low, high, and res to store the lower index, higher index, and the result index let low = 0; let high = index; let res = index; // Perform binary search to find the maximum frequency of the current element by varying the element to its left while (low <= high) { const mid = low + Math.floor((high - low) / 2); // Calculate the sum of the elements from mid to index const s = preSum[index + 1] - preSum[mid]; // Check if the sum can be increased by at most k by replacing the elements from mid to index with the current element nums[index] if (s + k >= (index - mid + 1) * nums[index]) { // If yes, update the result to mid and search for a better solution to the left of mid res = mid; high = mid - 1; } else { // If no, search for a better solution to the right of mid low = mid + 1; } } // Return the frequency of the current element return index - res + 1; } // Initialize a variable ans to store the maximum frequency let ans = 0; // Iterate over each element of the input array for (let i = 0; i < n; i++) { // Update the maximum frequency by taking the maximum of the current maximum frequency and the frequency of the current element ans = Math.max(ans, helper(i)); } // Return the maximum frequency return ans; } // Driver code const arr = [1, 4, 8, 13]; const K = 5; console.log( "Frequency of the Most Frequent Element: " + maxFrequency(arr, K)); |
Frequency of the Most Frequent Element : 2
Time Complexity: O(NlogN) where N is the size of the input vector
Auxiliary Space: O(N) where N is the size of the input vector. This is because we need to store the prefix sum vector which has N+1 elements, and the input vector after sorting has n elements.