1655. Distribute Repeating Integers
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
ithcustomer gets exactlyquantity[i]integers, - The integers the
ithcustomer 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
50unique values innums.
Solutions
Solution 1: State Compression Dynamic Programming + Subset Enumeration
First, we count the occurrence of each number in the array nums, and record it in the hash table cnt. Then we store the values in the hash table into the array arr. We denote the length of the array arr as n.
Note that the length of the array quantity does not exceed 10, so we can use a binary number to represent a subset of quantity. That is, the number j represents a subset of quantity, where the i-th bit of the binary representation of j is 1 means the i-th number in quantity is selected, and 0 means the i-th number is not selected.
We can preprocess an array s, where s[j] represents the sum of all numbers in the subset j of quantity.
Next, we define f[i][j] to represent whether the numbers in arr[0,..i-1] can be successfully allocated to the subset j of quantity, where i ranges from [0,..n-1], and j ranges from [0,2^m-1], where m is the length of quantity.
Considering f[i][j], if there exists a subset k in j such that s[k] <= arr[i], and f[i-1][j XOR k] is true, then f[i][j] is true, otherwise f[i][j] is false.
The answer is f[n-1][2^m-1].
The time complexity is O(n * 3^m), and the space complexity is O(n * 2^m). Here, n is the number of different integers in the array nums, and m is the length of the array quantity.
Python3
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]
Java
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];
}
}
C++
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];
}
};
Go
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]
}
TypeScript
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];
}