Description#
You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the ith customer ordered. Determine if it is possible to distribute nums such that:
- The
ith customer gets exactly quantity[i] integers, - The integers the
ith customer gets are all equal, and - Every customer is satisfied.
Return true if it is possible to distribute nums according to the above conditions.
Example 1:
Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.
Example 2:
Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.
Example 3:
Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= 1000m == quantity.length1 <= m <= 101 <= quantity[i] <= 105- There are at most
50 unique values in nums.
Solutions#
Solution 1#
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
| class Solution:
def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
m = len(quantity)
s = [0] * (1 << m)
for i in range(1, 1 << m):
for j in range(m):
if i >> j & 1:
s[i] = s[i ^ (1 << j)] + quantity[j]
break
cnt = Counter(nums)
arr = list(cnt.values())
n = len(arr)
f = [[False] * (1 << m) for _ in range(n)]
for i in range(n):
f[i][0] = True
for i, x in enumerate(arr):
for j in range(1, 1 << m):
if i and f[i - 1][j]:
f[i][j] = True
continue
k = j
while k:
ok1 = j == k if i == 0 else f[i - 1][j ^ k]
ok2 = s[k] <= x
if ok1 and ok2:
f[i][j] = True
break
k = (k - 1) & j
return f[-1][-1]
|
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
| class Solution {
public boolean canDistribute(int[] nums, int[] quantity) {
int m = quantity.length;
int[] s = new int[1 << m];
for (int i = 1; i < 1 << m; ++i) {
for (int j = 0; j < m; ++j) {
if ((i >> j & 1) != 0) {
s[i] = s[i ^ (1 << j)] + quantity[j];
break;
}
}
}
Map<Integer, Integer> cnt = new HashMap<>(50);
for (int x : nums) {
cnt.merge(x, 1, Integer::sum);
}
int n = cnt.size();
int[] arr = new int[n];
int i = 0;
for (int x : cnt.values()) {
arr[i++] = x;
}
boolean[][] f = new boolean[n][1 << m];
for (i = 0; i < n; ++i) {
f[i][0] = true;
}
for (i = 0; i < n; ++i) {
for (int j = 1; j < 1 << m; ++j) {
if (i > 0 && f[i - 1][j]) {
f[i][j] = true;
continue;
}
for (int k = j; k > 0; k = (k - 1) & j) {
boolean ok1 = i == 0 ? j == k : f[i - 1][j ^ k];
boolean ok2 = s[k] <= arr[i];
if (ok1 && ok2) {
f[i][j] = true;
break;
}
}
}
}
return f[n - 1][(1 << m) - 1];
}
}
|
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
| class Solution {
public:
bool canDistribute(vector<int>& nums, vector<int>& quantity) {
int m = quantity.size();
int s[1 << m];
memset(s, 0, sizeof(s));
for (int i = 1; i < 1 << m; ++i) {
for (int j = 0; j < m; ++j) {
if (i >> j & 1) {
s[i] = s[i ^ (1 << j)] + quantity[j];
break;
}
}
}
unordered_map<int, int> cnt;
for (int& x : nums) {
++cnt[x];
}
int n = cnt.size();
vector<int> arr;
for (auto& [_, x] : cnt) {
arr.push_back(x);
}
bool f[n][1 << m];
memset(f, 0, sizeof(f));
for (int i = 0; i < n; ++i) {
f[i][0] = true;
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j < 1 << m; ++j) {
if (i && f[i - 1][j]) {
f[i][j] = true;
continue;
}
for (int k = j; k; k = (k - 1) & j) {
bool ok1 = i == 0 ? j == k : f[i - 1][j ^ k];
bool ok2 = s[k] <= arr[i];
if (ok1 && ok2) {
f[i][j] = true;
break;
}
}
}
}
return f[n - 1][(1 << m) - 1];
}
};
|
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
| func canDistribute(nums []int, quantity []int) bool {
m := len(quantity)
s := make([]int, 1<<m)
for i := 1; i < 1<<m; i++ {
for j := 0; j < m; j++ {
if i>>j&1 == 1 {
s[i] = s[i^(1<<j)] + quantity[j]
break
}
}
}
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
n := len(cnt)
arr := make([]int, 0, n)
for _, x := range cnt {
arr = append(arr, x)
}
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, 1<<m)
f[i][0] = true
}
for i := 0; i < n; i++ {
for j := 0; j < 1<<m; j++ {
if i > 0 && f[i-1][j] {
f[i][j] = true
continue
}
for k := j; k > 0; k = (k - 1) & j {
ok1 := (i == 0 && j == k) || (i > 0 && f[i-1][j-k])
ok2 := s[k] <= arr[i]
if ok1 && ok2 {
f[i][j] = true
break
}
}
}
}
return f[n-1][(1<<m)-1]
}
|
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
| function canDistribute(nums: number[], quantity: number[]): boolean {
const m = quantity.length;
const s: number[] = new Array(1 << m).fill(0);
for (let i = 1; i < 1 << m; ++i) {
for (let j = 0; j < m; ++j) {
if ((i >> j) & 1) {
s[i] = s[i ^ (1 << j)] + quantity[j];
break;
}
}
}
const cnt: Map<number, number> = new Map();
for (const x of nums) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
const n = cnt.size;
const arr: number[] = [];
for (const [_, v] of cnt) {
arr.push(v);
}
const f: boolean[][] = new Array(n).fill(false).map(() => new Array(1 << m).fill(false));
for (let i = 0; i < n; ++i) {
f[i][0] = true;
}
for (let i = 0; i < n; ++i) {
for (let j = 0; j < 1 << m; ++j) {
if (i > 0 && f[i - 1][j]) {
f[i][j] = true;
continue;
}
for (let k = j; k > 0; k = (k - 1) & j) {
const ok1: boolean = (i == 0 && j == k) || (i > 0 && f[i - 1][j ^ k]);
const ok2: boolean = s[k] <= arr[i];
if (ok1 && ok2) {
f[i][j] = true;
break;
}
}
}
}
return f[n - 1][(1 << m) - 1];
}
|
