Distribute Repeating Integers

Problem

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.

Examples

Example 1

1
2
3


Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2

1
2
3


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

1
2
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].

Solution

Method 1 – Bitmask Dynamic Programming (Subset Assignment)

Intuition

We use bitmask DP to represent which customers have been satisfied. For each unique integer, we try all possible subsets of unsatisfied customers that can be satisfied with the available count. We update the DP accordingly.

Approach

Count the frequency of each unique integer in nums.
Sort quantity in descending order for pruning.
Use a DP array where dp[mask] is true if the subset of customers represented by mask can be satisfied.
For each unique integer, for each mask, try all subsets of unsatisfied customers that can be satisfied with the available count.
Update dp for the new mask.
The answer is dp[full_mask] (all customers satisfied).

Code

 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


class Solution {
public:
    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;
        vector<int> counts;
        for (auto& [k, v] : freq) counts.push_back(v);
        int m = quantity.size(), n = counts.size();
        vector<bool> dp(1<<m);
        dp[0] = true;
        for (int c : counts) {
            vector<bool> ndp = dp;
            for (int mask = 0; mask < (1<<m); ++mask) {
                if (!dp[mask]) continue;
                for (int sub = ((1<<m)-1)^mask; sub; sub = (sub-1)&(((1<<m)-1)^mask)) {
                    int sum = 0;
                    for (int i = 0; i < m; ++i) if (sub & (1<<i)) sum += quantity[i];
                    if (sum <= c) ndp[mask|sub] = true;
                }
            }
            dp = ndp;
        }
        return dp[(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


func canDistribute(nums []int, quantity []int) bool {
    freq := map[int]int{}
    for _, x := range nums {
        freq[x]++
    }
    counts := []int{}
    for _, v := range freq {
        counts = append(counts, v)
    }
    m, n := len(quantity), len(counts)
    dp := make([]bool, 1<<m)
    dp[0] = true
    for _, c := range counts {
        ndp := make([]bool, 1<<m)
        copy(ndp, dp)
        for mask := 0; mask < (1<<m); mask++ {
            if !dp[mask] {
                continue
            }
            for sub := ((1<<m)-1)^mask; sub > 0; sub = (sub-1)&(((1<<m)-1)^mask) {
                sum := 0
                for i := 0; i < m; i++ {
                    if sub&(1<<i) > 0 {
                        sum += quantity[i]
                    }
                }
                if sum <= c {
                    ndp[mask|sub] = true
                }
            }
        }
        dp = ndp
    }
    return dp[(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


class Solution {
    public boolean canDistribute(int[] nums, int[] quantity) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        List<Integer> counts = new ArrayList<>(freq.values());
        int m = quantity.length, n = counts.size();
        boolean[] dp = new boolean[1<<m];
        dp[0] = true;
        for (int c : counts) {
            boolean[] ndp = dp.clone();
            for (int mask = 0; mask < (1<<m); ++mask) {
                if (!dp[mask]) continue;
                for (int sub = ((1<<m)-1)^mask; sub > 0; sub = (sub-1)&(((1<<m)-1)^mask)) {
                    int sum = 0;
                    for (int i = 0; i < m; ++i) if ((sub & (1<<i)) > 0) sum += quantity[i];
                    if (sum <= c) ndp[mask|sub] = true;
                }
            }
            dp = ndp;
        }
        return dp[(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


class Solution {
    fun canDistribute(nums: IntArray, quantity: IntArray): Boolean {
        val freq = nums.groupingBy { it }.eachCount()
        val counts = freq.values.toList()
        val m = quantity.size
        var dp = BooleanArray(1 shl m)
        dp[0] = true
        for (c in counts) {
            val ndp = dp.copyOf()
            for (mask in 0 until (1 shl m)) {
                if (!dp[mask]) continue
                var sub = ((1 shl m) - 1) xor mask
                while (sub > 0) {
                    var sum = 0
                    for (i in 0 until m) if ((sub and (1 shl i)) > 0) sum += quantity[i]
                    if (sum <= c) ndp[mask or sub] = true
                    sub = (sub - 1) and (((1 shl m) - 1) xor mask)
                }
            }
            dp = ndp
        }
        return dp[(1 shl m) - 1]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def canDistribute(self, nums: list[int], quantity: list[int]) -> bool:
        from collections import Counter
        freq = Counter(nums)
        counts = list(freq.values())
        m = len(quantity)
        dp = [False] * (1<<m)
        dp[0] = True
        for c in counts:
            ndp = dp[:]
            for mask in range(1<<m):
                if not dp[mask]: continue
                sub = ((1<<m)-1) ^ mask
                while sub:
                    sumq = sum(quantity[i] for i in range(m) if sub & (1<<i))
                    if sumq <= c:
                        ndp[mask|sub] = True
                    sub = (sub-1) & (((1<<m)-1) ^ mask)
            dp = ndp
        return dp[(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


impl Solution {
    pub fn can_distribute(nums: Vec<i32>, quantity: Vec<i32>) -> bool {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for x in nums { *freq.entry(x).or_insert(0) += 1; }
        let counts: Vec<i32> = freq.values().copied().collect();
        let m = quantity.len();
        let mut dp = vec![false; 1<<m];
        dp[0] = true;
        for &c in &counts {
            let mut ndp = dp.clone();
            for mask in 0..(1<<m) {
                if !dp[mask] { continue; }
                let mut sub = ((1<<m)-1) ^ mask;
                while sub > 0 {
                    let mut sum = 0;
                    for i in 0..m { if (sub & (1<<i)) > 0 { sum += quantity[i]; } }
                    if sum <= c { ndp[mask|sub] = true; }
                    sub = (sub-1) & (((1<<m)-1) ^ mask);
                }
            }
            dp = ndp;
        }
        dp[(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


class Solution {
    canDistribute(nums: number[], quantity: number[]): boolean {
        const freq = new Map<number, number>()
        for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1)
        const counts = Array.from(freq.values())
        const m = quantity.length
        let dp = Array(1<<m).fill(false)
        dp[0] = true
        for (const c of counts) {
            const ndp = dp.slice()
            for (let mask = 0; mask < (1<<m); ++mask) {
                if (!dp[mask]) continue
                let sub = ((1<<m)-1) ^ mask
                while (sub) {
                    let sum = 0
                    for (let i = 0; i < m; ++i) if (sub & (1<<i)) sum += quantity[i]
                    if (sum <= c) ndp[mask|sub] = true
                    sub = (sub-1) & (((1<<m)-1) ^ mask)
                }
            }
            dp = ndp
        }
        return dp[(1<<m)-1]
    }
}

Complexity

⏰ Time complexity: O(n * 2^m * m) — n is the number of unique integers, m is the number of customers.
🧺 Space complexity: O(2^m) — For the DP array.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Solution#

Method 1 – Bitmask Dynamic Programming (Subset Assignment)#

Intuition#

Approach#

Code#

Complexity#