There are n products in an Amazon catalogue, where the category of the ith product is represented by the array catalogue.
The catalogue will be called valid if the number of distinct product categories in it is at most k. If the catalogue is not valid initially, then make it valid by removing some products from the catalogue.
Given n products and an array catalogue, find the minimum number of products to remove from the catalogue to make it valid.
Function Description
Complete the function getminRemoval in the editor below.
getminRemoval has the following parameter(s):
int catalogue[n]: the category of the productsint k: the maximum number of distinct product categories
Returns
int: the minimum number of elements to remove from catalogue to make it valid.
Example 1:
Input: catalogue = [3, 3, 5, 7], k = 1
Output: 2
Explanation:We can also remove [3, 3, 5] or [3, 3, 7]. However, the number of removed products in these cases is 3, which is not the minimum. Hence, the answer is 2.
1 ≤ n ≤ 10^51 ≤ k ≤ 10^51 ≤ catalogue[i] ≤ 10^5
input:
output: