2910. Minimum Number of Groups to Create a Valid Assignment
You are given a 0-indexed integer array nums of length n.
We want to group the indices so for each index i in the range [0, n - 1], it is assigned to exactly one group.
A group assignment is valid if the following conditions hold:
- For every group
g, all indices i assigned to group g have the same value in nums.
- For any two groups
g1 and g2, the difference between the number of indices assigned to g1 and g2 should not exceed 1.
Return an integer denoting the minimum number of groups needed to create a valid group assignment.
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
| class Solution {
public:
int minGroupsForValidAssignment(vector<int>& nums) {
unordered_map<int, int> freq;
for(auto& n : nums) freq[n] += 1;
unordered_map<int, int> gc;
int mi = 1e9;
for(auto& [_,v] : freq) {
mi = min(mi, v);
gc[v] += 1;
}
auto can = [&](int cnt, int target, bool fl) {
int d = cnt / target, r = cnt % target;
if(r == 0) return true;
if(!fl) return false;
int x = target - r;
return d >= x;
};
auto sum = [&](int cnt, int target) {
int d = cnt / target, r = cnt % target;
if(r == 0) return d;
return d + 1;
};
for(int i = mi; i >= 1; i--) {
bool ok = true;
long long now = 0;
for(auto& [g,cnt] : gc) {
int gg = g;
if(can(gg,i+1,true)) {
now += cnt * sum(gg,i+1);
} else if(can(gg,i,false)) {
now += cnt * sum(gg,i);
} else ok = false;
if(!ok) break;
}
if(ok) {
return now;
}
}
return -1;
}
};
|
