Reduce Array Size to The Half

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
Paytm (One97 Communications Limited)InfosysMeesho

Problem statement

Your friend gifted you ‘N’ balls. Each ball has a number associated with it, the numbers associated with the balls are given in the array 'ARR'. But your cupboard has slots such that only N/2 balls can be kept. So, you decided to remove the balls following an operation.

In one operation, you can select a ball numbered ‘x’ and remove all the balls which are numbered ‘x’.

You are supposed to minimize the number of operations such that at least half of the balls are removed from ‘N’ balls.

Note:

Numbers on the balls may not be unique.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line contains integer ‘N’, which denotes the number of elements in the array ‘ARR’.

The second line contains N integers denoting the elements of the array ‘ARR’.
Output Format: 
For each test case, return the minimum number of operations you need to perform to remove at least half of the balls.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1<= T <= 50
1 <= N <= 10^4
N is always even.
1 <= ARR[i] <= 10^9

Time Limit: 1 sec
Sample Input 1:
2
6
2 1 4 1 2 2
10
2 1 4 1 2 2 3 3 3 3
Sample Output 1:
1
2
Explanation for Sample Input 1:
In the first test case, 6 balls are given numbered [2, 1, 4, 2, 2 ,2].
In order to remove at least 3 balls, the most efficient approach is to remove all the balls numbered ‘2’ as there are 4 balls numbered ‘2’. The number of remaining balls will be 2. So, the answer is 1.

In the second test case, 10 balls are given numbered [2, 1, 4, 2, 2 ,2, 3, 3, 3, 3].
In order to remove at least 5 balls, the most efficient approach is to remove all the balls numbered ‘2’ and ‘3’ as there are 4 balls numbered ‘2’ and 4 balls numbered ‘3’.The number of remaining balls will be 2. So, the answer is 2.
Sample Input 2:
2
14
4 5 6 4 5 2 4 5 6 2 4 5 5 4 
8
1 1 2 2 3 3 4 4
Sample Output 2:
2
2
Hint

Think of removing the balls which have the maximum number of occurrences. 

Approaches (1)
Greedy

The idea is to traverse the array and count the number of occurrences and store it in a hashmap. After that traverse in the hashmap and sort the elements in descending order of their occurrences. Then delete the element which has the occurs maximum number of times, then the second maximum, etc until at least n/2 elements are not deleted.

 

The steps are as follows:

  • Declare a hashmap 'COUNT_OCCURENCES' which stores the number associated with the balls as the key and their occurrences as the values.
  • Iterate over the array 'ARR':
    • If the current element is 'CURRENT', increment the count of 'CURRENT' in the hashMap 'COUNT_OCCURENCES'.
  • Declare an array 'DESCENDING_OCCURENCES' that stores the occurrences of elements in descending order.
  • Iterate over the hashmap 'COUNT_OCCURENCES':
    • Push the number of occurrences of the current element in the array 'DESCENDING_OCCURENCES'.
  • Sort the array 'DESCENDING_OCCURENCES' in descending order.
  • Initialize two integers 'ANS', and 'REMOVED' to 0 which denotes the final answer and the number of elements that we removed.
  • Iterate over the array 'DESCENDING_OCCURENCES':
    • Add the current element into 'REMOVED' and increment 'ANS' by 1.
    • If 'REMOVED' becomes greater than N/2, return the 'ANS' as the final answer.
Time Complexity

O(N*log(N)), where ‘N’ is the number of balls given.

 

As we are sorting the array storing the frequency of each number which in the worst case takes N*log(N) time. Hence, the overall time complexity is O(N*log(N)).

Space Complexity

O(N), where ‘N’ is the number of balls given.

 

As we are using array ‘descendingOccurences’ and a hashmap ‘countOccurences’ which may grow up to a size of ‘N’ in the worst case. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Reduce Array Size to The Half
Full screen
Console