Orange-Bloom/Minimum Distinct Ids.java at master · aky91/Orange-Bloom · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Akash Yadav
// @PD Tandon, MNNIT, Allahabad
// 28th July 18

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

class Ideone{

	//https://practice.geeksforgeeks.org/problems/minimum-distinct-ids/0

	public static Scanner scn = new Scanner(System.in);

	public static void main (String[] args) throws java.lang.Exception{

		int T = scn.nextInt();

		while(T-- > 0){

			int N = scn.nextInt();

			int[] arr = new int[N];

			for(int i = 0; i < N ; i++)
			    arr[i] = scn.nextInt();

            int K = scn.nextInt();

            HashMap<Integer, Integer> map = new HashMap<>();

            for(int i = 0; i < N; i++){

                int data = arr[i];

                if(!map.containsKey(data)) map.put(data, 0);

                map.put(data, map.get(data) + 1);
            }

            ArrayList<Integer> list = new ArrayList<>(map.keySet());

            int[][] res = new int[list.size()][2];

            for(int i = 0; i < list.size(); i++){

                int data = list.get(i);
                int freq = map.get(data);

                res[i][0] = data;
                res[i][1] = freq;
            }

            Arrays.sort(res, new Comparator<int[]>(){

                public int compare(int[] A, int[] B){

                    int a = A[1];
                    int b = B[1];

                    return a-b;
                }
            });

            // for(int i = 0; i < list.size(); i++)
            //     System.out.println("" + res[i][0] + " " + res[i][1]);

            int m = list.size();

            for(int i = 0; i < m && K > 0;){

                if(res[i][1] <= 0){
                    i++;
                    continue;
                }

                res[i][1]--;
                K--;
            }

            int ans = 0;

            for(int i = 0; i < list.size(); i++)
                if(res[i][1] != 0) ans++;

            System.out.println(ans + "");
		}

	}
}