Maximum equal elements after K operations
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

Question

Maximum equal elements after K operations

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

Accepted Answer

This was a very easy question as I just had to traverse both the array and maintain a count variable and a variable to store last maximum equal element encountered which I initialized to a very small number (like INT_MIN in C++) . Now while traversing whenever you encounter equal elements which are greater than last maximum equal elements then increment count by 1. In the end just print count.

Accepted Answer

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:

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.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra memory.

Time Complexity: O(n^2)Explanation:

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

Because we run two loops over the input array.

Accepted Answer

Binary Search

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.

Space Complexity: O(n)Explanation:

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

As we are using extra space for preSum array.

Time Complexity: O(nlogn)Explanation:

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

As time complexity for binary search is O(logN) and in each iteration, we perform a sliding window search. Hence multiply logN by N to get the final time complexity.

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:

Input Format:

Output Format:

Note:

Constraints:

Top Visa Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Visa Software Developer