Last Updated: 28 Dec, 2020
Maximum Equal Elements After K Operations
Moderate
Asked in companies
You are given an arbitrary array/list of integers 'ARR' of size ‘N’ and an integer ‘K’. You need to find the maximum number of elements which can be made equal to each other after performing at most K operations.
An operation is defined as "Choosing an element from 'ARR' and increasing it by 1".
Note:
You can perform multiple operations on a single element also.
Input Format:
The first line of the input contains a single integer T, representing the number of test cases.
The first line of each test case consists of two space-separated integers, representing the values of N (size of 'ARR') and K(maximum number of updates possible).
The second line of each test case contains N space-separated integers, denoting the elements of the 'ARR'.
Output Format:
For each test case, print a single integer, representing the maximum number of elements that can be made equal after performing K or fewer increments.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^2
1 <= N <= 10^3
1 <= ARR[i], K <= 10^9
Time Limit: 1sec
Approaches
Approach: To find the maximum count of equal elements after performing K increments, a naive approach will be to consider every array element and try making all other elements equal to it within the constraint of doing at most K increments. In whichever case we get the maximum number of equal elements, we store it in our ‘ans’ variable and return it in the end.
We will have to sort the input array in order for this algorithm to work. After that, we run two loops- outer loop(for i) from N - 1 to 0th index which will be used for fixing the array element to which we will try to increment all other elements that are currently less than it; and an inner loop which will go from (i - 1) to 0th index to keep track of remaining updates(stored in ‘remaining’) and current number of equal elements(stored in ‘curr’). We update our final ‘ans’ variable whenever curr>ans.
Algorithm:
- Sort the input array.
- Initialize ‘ANS’ = 1, ‘CURR’ = 1, 'REMAINING' = ‘K’.
- For 'i' = ‘N’ - 1 to 0
- Make ‘CURR’ = 1 and ‘REMAINING’ = ‘K’ for a fresh iteration.
- For 'j' = ‘i’ - 1 to 0
- If the difference between ARR[j] and ARR[i] is less then or equal to ‘REMAINING’, increment ‘CURR’ by 1, and update ‘REMAINING’ and ‘ANS’.
- Else, break out of the loop as we cannot make any more elements equal to fixed.
- Return ‘ANS’ and terminate.
Approach: An efficient way to solve this problem is to first sort the array and then use binary search on the sorted array. In binary search, we will try to find a range of ‘X’ elements in the given array for which all elements in the range ’X’ can be made equal in at most K operations. For doing this, we maintain an auxiliary array ‘PRESUM’ size ‘N’ + 1. ‘PRESUM[i]’ will indicate the prefix sum from 0 to ith index.
In binary search, we use a helper function ‘helper’ to determine whether any ‘X’ elements can be made equal to each other or not. The value of ‘X’ will be the midpoint of low and high points in the binary search at any point. Initially, low = 1(the least possible answer) and high = N(the maximum possible answer). In the helper function, we use a sliding window to determine whether there are x number of elements present which when incremented will become equal. Now, while checking for different windows using a for loop, the condition to be checked will be:-
(X * ARR[j - 1] - (PRESUM[j] - PRESUM[i] )) <= K, where i and j are the starting and ending indices of the sliding window.
We update our ‘ANS’ variable based on the output of the helper function and also update the starting and ending points of binary search accordingly.
Similar problems