SHOW:
|
|
- or go back to the newest paste.
1 | // Author : Saurav Kalsoor | |
2 | - | // Sort By Primes - JAVA |
2 | + | // Minimize Unique Numbers - JAVA |
3 | ||
4 | import java.util.*; | |
5 | ||
6 | public class Test { | |
7 | static Scanner sc = new Scanner(System.in); | |
8 | public static void main(String[] args) { | |
9 | int n = sc.nextInt(); | |
10 | int k = sc.nextInt(); | |
11 | ||
12 | ArrayList<Integer> arr = new ArrayList<>(); | |
13 | for(int i = 0;i < n; i++){ | |
14 | - | for(int i=0; i < n; i++) { |
14 | + | arr.add(sc.nextInt()); |
15 | - | int input = sc.nextInt(); |
15 | + | } |
16 | - | arr.add(input); |
16 | + | |
17 | - | } |
17 | + | System.out.println(minimizeUnique(arr, k)); |
18 | } | |
19 | - | ArrayList<Integer> result = sortPrimeNonPrime(arr, n); |
19 | + | |
20 | public static int minimizeUnique(ArrayList<Integer> arr, int k){ | |
21 | - | for(int i=0; i < n; i++) |
21 | + | HashMap<Integer, Integer> count = new HashMap<>(); |
22 | - | System.out.print(result.get(i) + " "); |
22 | + | |
23 | for(int num : arr){ | |
24 | - | System.out.println(); |
24 | + | count.put(num, count.getOrDefault(num, 0) + 1); |
25 | } | |
26 | ||
27 | - | public static ArrayList<Integer> sortPrimeNonPrime(ArrayList<Integer> arr, int n){ |
27 | + | Set<MyPair> st = new TreeSet<>(new Comparator<MyPair>() { |
28 | @Override | |
29 | - | int maxLimit = 10001; |
29 | + | public int compare(MyPair a, MyPair b) { |
30 | - | HashSet<Integer> primesSet = new HashSet<>(); |
30 | + | if(a.second == b.second) |
31 | - | boolean[] isPrime = new boolean[maxLimit]; |
31 | + | return a.first - b.first; |
32 | return a.second - b.second; | |
33 | - | for(int i=2; i < maxLimit; i++) isPrime[i] = true; |
33 | + | } |
34 | }); | |
35 | - | for(int i=2; i < maxLimit; i++){ |
35 | + | |
36 | - | if(isPrime[i]){ |
36 | + | for(Map.Entry<Integer, Integer> x : count.entrySet()){ |
37 | - | primesSet.add(i); |
37 | + | st.add(new MyPair(x.getKey(), x.getValue()) ); |
38 | - | for(int j = i*i ; j < maxLimit; j += i) |
38 | + | } |
39 | - | isPrime[j] = false; |
39 | + | |
40 | - | } |
40 | + | int res = st.size(); |
41 | - | } |
41 | + | |
42 | for(MyPair x : st){ | |
43 | - | ArrayList<Integer> primes = new ArrayList<Integer>(); |
43 | + | if(k >= x.second){ |
44 | - | ArrayList<Integer> nonPrimes = new ArrayList<Integer>(); |
44 | + | res--; |
45 | k -= x.second; | |
46 | - | for(int i=0; i < n; i++){ |
46 | + | }else{ |
47 | - | if(primesSet.contains(arr.get(i))){ |
47 | + | break; |
48 | - | primes.add(arr.get(i)); |
48 | + | } |
49 | - | }else{ |
49 | + | } |
50 | - | nonPrimes.add(arr.get(i)); |
50 | + | |
51 | - | } |
51 | + | return res; |
52 | - | } |
52 | + | |
53 | ||
54 | - | Collections.sort(primes); |
54 | + | |
55 | - | Collections.sort(nonPrimes, Collections.reverseOrder()); |
55 | + | |
56 | class MyPair{ | |
57 | - | ArrayList<Integer> result = new ArrayList<Integer>(); |
57 | + | public int first, second; |
58 | ||
59 | - | int j = 0, k = 0; |
59 | + | public MyPair(int first, int second){ |
60 | - | for(int i=0; i < n; i++){ |
60 | + | this.first = first; |
61 | - | if(primesSet.contains(arr.get(i))){ |
61 | + | this.second = second; |
62 | - | result.add(primes.get(j)); |
62 | + | } |
63 | - | j++; |
63 | + | |
64 | - | }else{ |
64 | + | |
65 | - | result.add(nonPrimes.get(k)); |
65 | + | |
66 | - | k++; |
66 | + |