package com.fishercoder.solutions;

import java.util.Collections;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 1338. Reduce Array Size to The Half
 *
 * Given an array arr.  You can choose a set of integers and remove all the occurrences of these integers in the array.
 * Return the minimum size of the set so that at least half of the integers of the array are removed.
 *
 * Example 1:
 * Input: arr = [3,3,3,3,5,5,5,2,2,7]
 * Output: 2
 * Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
 * Possible sets of size 2 are {3,5},{3,2},{5,2}.
 * Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.
 *
 * Example 2:
 * Input: arr = [7,7,7,7,7,7]
 * Output: 1
 * Explanation: The only possible set you can choose is {7}. This will make the new array empty.
 *
 * Example 3:
 * Input: arr = [1,9]
 * Output: 1
 *
 * Example 4:
 * Input: arr = [1000,1000,3,7]
 * Output: 1
 *
 * Example 5:
 * Input: arr = [1,2,3,4,5,6,7,8,9,10]
 * Output: 5
 *
 * Constraints:
 * 1 <= arr.length <= 10^5
 * arr.length is even.
 * 1 <= arr[i] <= 10^5
 * */
public class _1338 {
    public static class Solution1 {
        public int minSetSize(int[] arr) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i : arr) {
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
            List<Integer> list = new ArrayList<>();
            for (int k : map.keySet()) {
                list.add(map.get(k));
            }
            Collections.sort(list, Collections.reverseOrder());
            int sum = 0;
            int i = 0;
            while (sum < arr.length / 2) {
                sum += list.get(i++);
            }
            return i--;
        }
    }
}

@@ -163,1133 +163,659 @@
 p;%0A%0A
-/**%0A * 1338. Reduce Array Size to The Half%0A *%0A * Given an array arr.  You can choose a set of integers and remove all the occurrences of these integers in the array.%0A * Return the minimum size of the set so that at least half of the integers of the array are removed.%0A *%0A * Example 1:%0A * Input: arr = %5B3,3,3,3,5,5,5,2,2,7%5D%0A * Output: 2%0A * Explanation: Choosing %7B3,7%7D will make the new array %5B5,5,5,2,2%5D which has size 5 (i.e equal to half of the size of the old array).%0A * Possible sets of size 2 are %7B3,5%7D,%7B3,2%7D,%7B5,2%7D.%0A * Choosing set %7B2,7%7D is not possible as it will make the new array %5B3,3,3,3,5,5,5%5D which has size greater than half of the size of the old array.%0A *%0A * Example 2:%0A * Input: arr = %5B7,7,7,7,7,7%5D%0A * Output: 1%0A * Explanation: The only possible set you can choose is %7B7%7D. This
+public class _1338 %7B%0A    public static class Solution1 %7B%0A        public int minSetSize(int%5B%5D arr) %7B%0A            Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A            for (int i : arr) %7B%0A                map.put(i, map.getOrDefault(i, 0) + 1);%0A            %7D%0A            List%3CInteger%3E list = new ArrayList%3C%3E();%0A            for (int k : map.keySet()) %7B%0A                list.add(map.get(k));%0A            %7D%0A            Collections.sort(list, Collections.reverseOrder());%0A            int sum = 0;%0A            int i = 0;%0A           
  w
+h
 il
-l make the new array empty.%0A *%0A * Example 3:%0A * Input: arr = %5B1,9%5D%0A * Output: 1%0A *%0A * Example 4:%0A * Input: arr = %5B1000,1000,3,7%5D%0A * Output: 1%0A *%0A * Example 5:%0A * Input: arr = %5B1,2,3,4,5,6,7,8,9,10%5D%0A * Output: 5%0A *%0A * Constraints:%0A * 1 %3C= arr.length %3C= 10%5E5%0A * arr.length is even.%0A * 1 %3C= arr%5Bi%5D %3C= 10%5E5%0A * */%0Apublic class _1338 %7B
+e (sum %3C arr.length / 2) %7B%0A                sum += list.get(i++);%0A            %7D%0A            return i--;%0A        %7D%0A    %7D%0A
 %0A   
@@ -835,33 +835,33 @@
 c class Solution
-1
+2
  %7B%0A        publi
@@ -960,33 +960,35 @@
        for (int 
-i
+num
  : arr) %7B%0A      
@@ -997,33 +997,35 @@
         map.put(
-i
+num
 , map.getOrDefau
@@ -1019,33 +1019,35 @@
 ap.getOrDefault(
-i
+num
 , 0) + 1);%0A     
@@ -1064,39 +1064,37 @@
            List%3C
-Integer
+int%5B%5D
 %3E list = new Arr
@@ -1119,32 +1119,34 @@
       for (int k
+ey
  : map.keySet())
@@ -1169,34 +1169,52 @@
    list.add(
-map.get(k)
+new int%5B%5D%7Bmap.get(key), key%7D
 );%0A         
@@ -1257,35 +1257,58 @@
 st, 
-Collections.reverseOrder())
+(a, b) -%3E b%5B0%5D - a%5B0%5D);%0A            int minSet = 0
 ;%0A  
@@ -1313,35 +1313,37 @@
             int 
-sum
+count
  = 0;%0A          
@@ -1348,99 +1348,193 @@
     
-int i = 0;%0A            while (sum %3C arr.length / 2) %7B%0A                sum += list.get(i++);
+for (int%5B%5D pair : list) %7B%0A                count += pair%5B0%5D;%0A                minSet++;%0A                if (count %3E= arr.length / 2) %7B%0A                    return minSet;%0A                %7D
 %0A   
@@ -1555,35 +1555,38 @@
          return 
-i--
+minSet
 ;%0A        %7D%0A    

add a solution for 1338