# 2910. Minimum Number of Groups to Create a Valid Assignment

no need to use BS, we only have some choice to pick (1 to least freq)

```
T: O(n)
S: O(n)
```

````java
```java
class Solution {
    public int minGroupsForValidAssignment(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        // only one kind of number -> so return 1 group
        List<Integer> freq = new ArrayList<>(map.values()); // ex: group size: 5 4 3
        if (freq.size() == 1) {
            return 1;
        }

        int leastFreq = Integer.MAX_VALUE;
        for (int f : freq) {
            leastFreq = Math.min(leastFreq, f);
        }

        // try from 1 to leastFreq size to seperate groups
        // 5 4 3 -> try 1(x), 2()
        int result = nums.length;
        for (int i = 1; i <= leastFreq; i++) {
            result = Math.min(result, getGroups(i, freq));
        }
        return result;
    }
    private int getGroups(int size, List<Integer> freq) {
        int result = 0;
        for (int f : freq) {
            int groups = f / size; // 5/2 = 2. ;   4/2 = 2. ; 3/2 = 1
            int remaining = f % size; // 5%2 = 1. ; 4%2 = 0 ; 3%2 = 1
            if (remaining > groups) { 
                return Integer.MAX_VALUE;
            }
            result += Math.ceil((double)f/(size+1)); // 5/3 = 1.68 = 2. ; 2 ;  3/(2+1) = 1
        }
        return result; // 2+2+1 = 5, so using size 2 is ok!
    }
}

/**
using 3
int groups    = f / size; // 5/3 = 1. ;   4/2 = 2. ; 3/2 = 1
int remaining = f % size; // 5%3 = 2. ; 4%2 = 0 ; 3%2 = 1
if (2 > 1) { -> return MAX_VALUE -> end

so the ans is using size 2, result = 5

T: O(n)
S: O(n)
 */
```
````
