A salesperson must sell n items in a bag with random IDs. The salesperson can remove as many as m items from the bag. Determine the minimum number of different IDs the final bag can contain after performing, at most, m deletions.
Example
n = 6
ids = [1, 1, 1, 2, 3, 2]
m = 2
Two possible actions that give the minimum 2 different IDs:
- Remove 2 items with ID = 2 and the final bag will contain item ids' = [1, 1, 1, 3]
- Remove 1 item with ID = 2 and 1 item with ID=3 and the final bag will contain item ids' = [1, 1, 1, 2]
The minimum number of distinct IDs is 2.
Function Description
Complete the function deleteProducts in the editor below.
deleteProducts has the following parameters:
int ids[n]: an array of integers
int m: an integer, the maximum number of deletions
Returns:
int: an integer that represents the minimum number of item IDs
Constraints
- 1 ≤ n ≤ 105
- 1 ≤ ids[i] ≤ 106
- 1 ≤ m ≤ 105
Input Format For Custom Testing
The first line contains an integer, n, that denotes the number of elements in ids. Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer ids[i].
The last line contains an integer, m, that denotes the maximum number of items that can be deleted.
Sample Case 0
Sample Input
STDIN Function ----- ----- 4 → ids[] size n = 4 1 → ids = [1, 1, 5, 5] 1 5 5 2 → m = 2
Sample Output
1
Explanation
Two possible actions that give 1 as the minimum number of different IDs:
- Remove 2 items with ID = 1 and the final bag will contain item ids' = [5, 5]
- Remove 2 items with ID = 5 and the final bag will contain item ids' = [1, 1]
Sample Case 1
Sample Input
STDIN Function ----- ----- 7 → ids[] size n = 7 1 → ids = [1, 2, 3, 1, 2, 2, 1] 2 3 1 2 2 1 3 → m = 3
Sample Output
2
Explanation
Three possible actions that give 2 as the minimum number of different IDs:
- Remove 3 items with ID = 1 and the final bag will contain item ids' = [2, 3, 2, 2]
- Remove 3 items with ID = 2 and the final bag will contain item ids' = [1, 3, 1, 1]
- Remove 1 item with ID = 3 and the final bag will contain item ids' = [1, 2, 1, 2, 2, 1]
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
public class Result {
/*
* Complete the 'deleteProducts' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER_ARRAY ids
* 2. INTEGER m
*/
public static int deleteProducts(List<Integer> ids, int m) {
// Write your code here
Map<Integer, Integer> map = new HashMap<>();
for (Integer id : ids) {
if (map.containsKey(id)) {
map.put(id, map.get(id) + 1);
} else {
map.put(id, 1);
}
}
// values
List<Map.Entry<Integer, Integer>> list = new LinkedList<>(map.entrySet());
// sorting using Comparator
list.sort(Comparator.comparingInt(Map.Entry::getValue));
// Creating new map after sorting and also
// maintaining insertion order
Map<Integer, Integer> lh = new LinkedHashMap<>();
for (Map.Entry<Integer, Integer> e : list) {
lh.put(e.getKey(), e.getValue());
}
for (Integer i : lh.keySet()) {
// removing element from whose frequency count is
// less than m ,Sorted manner to get minimum
// distinct ids
if (map.get(i) <= m) {
m -= map.get(i);
map.remove(i);
}
}
return map.size();
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int idsCount = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> ids = IntStream.range(0, idsCount).mapToObj(i -> {
try {
return bufferedReader.readLine().replaceAll("\\s+$", "");
} catch (IOException ex) {
throw new RuntimeException(ex);
}
})
.map(String::trim)
.map(Integer::parseInt)
.collect(toList());
int m = Integer.parseInt(bufferedReader.readLine().trim());
int result = Result.deleteProducts(ids, m);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}