Maximum Equal Elements After K Operations

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in companies
MakeMyTripVisa

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
3 4
1 3 8
Sample Output 1:
2
Explanation For Sample Input 1:
Here, 'K' = 4 hence we can perform at most 4 increments. Clearly, the difference between 3 and 8 is 5, which is more than K(4), hence we cannot make 1 or 3 equal to 8. Trying to make the elements equal to 3, we can increment ARR[0] by 2, so that the array becomes [3, 3, 8]. In this configuration, we have 2 array elements equal. Hence, the answer will be 2.
Sample Input 2:
1
4 5
1 3 5 5
Sample Output 2:
3
Explanation For Sample Input 2:
Here, two elements are already 5 and we can increment 3 twice to get three 5’s, making ARR[] = {1, 5, 5, 5}. Hence the answer will be 3.
Hint

Think you can solve this if array is sorted

Approaches (2)
Naive Approach

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:

  1. Sort the input array.
  2. Initialize ‘ANS’ = 1, ‘CURR’ = 1, 'REMAINING' = ‘K’.
  3. 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.
  4. Return ‘ANS’ and terminate.
Time Complexity

O(N ^ 2), where ‘N’ is the number of elements in the array.

 

Because we run two loops over the input array.

Space Complexity

O(1).

 

As we are using constant extra memory.

Code Solution
(100% EXP penalty)
Maximum Equal Elements After K Operations
Full screen
Console