1655. Distribute Repeating Integers


Problem Description

You have been given two arrays: nums and quantity. The array nums consists of n integers which may have at most 50 unique values. The quantity array has m different customer order quantities, where quantity[i] signifies the number of integers the ith customer needs to order. The challenge is to determine whether it is possible to distribute the integers from the nums array to fulfill the following conditions:

  1. Each ith customer should receive exactly quantity[i] number of integers.
  2. All the integers a customer receives must be identical.
  3. All customers should have their orders satisfied as per the first two conditions.

The goal is to return true if it is indeed possible to disseminate the integers contained in nums to satisfy all customers as described by the conditions.

Intuition

To find the solution to this problem, we can think in terms of subsets and dynamic programming. Here are the key steps on how we can approach the problem:

  1. Generate all possible subsets of order quantities that can be fulfilled.
  2. Use a counter or map to keep track of the number of times each unique value appears in the nums array since each customer needs to receive the same number of identical integers.
  3. Utilize dynamic programming where each state represents whether a given subset of customer orders can be satisfied with a selection of integers from the nums array.
  4. For every unique integer in the nums array, iterate over all possible customer order subsets to determine if the current integer can fulfill some or all of the orders in the subset.
  5. Since the dynamic programming dimension is 2^m (where m is the number of customers/orders), we need to iterate over all states and try to partition the state into two parts: the one which could be satisfied by previous numbers (if not the first) and the one which needs to be satisfied by the current number.

By iterating over the nums array and updating our dynamic programming table to keep track if we can satisfy customers' orders with the quantities we have, we will finally reach a conclusion. If the final state—representing all customers' orders being fulfilled—can be reached, we return true, otherwise, false.

The provided code implements this approach with an efficient bit manipulation strategy to manage subsets and dynamic programming states.

Solution Approach

The solution uses bit manipulation and dynamic programming to approach this problem.

Firstly, the solution calculates all possible sums of quantity using bit manipulation. The s array is used to store sums for different combinations of customers’ order quantities (quantity) based on the subset of customers chosen, which can be represented by a bit mask. This is done using the first for loop.

Then, a counter for nums is used to determine how many times each unique value appears. This is important as it dictates the maximum number of orders that can be fulfilled by that integer. The values from the counter are then stored in the arr list.

The dynamic programming table f is initialized as a 2D array filled with False, with dimensions [n][1 << m], where n is the number of unique integers in nums and m is the number of customer orders. Here, f[i][j] means whether it is possible to fulfill the subset of orders represented by j using the first i integers.

The first column of the DP table is set to True to represent that the subset of orders with no orders (empty subset) can always be fulfilled regardless of the available integers.

By looping through each integer x available (arr) and for each subset of orders, the code updates the DP table f. The nested loops go over each combination j of orders and attempt to reduce it to a smaller subset k by fulfilling some orders using the current integer x.

  • If j is equal to k (or if f[i-1][j^k] is True for non-first integers), it means previous integers (up to i-1) can already fulfill the other part of orders (j^k).
  • If s[k] is less than or equal to x, it means x can be used to fulfill the orders in subset k.

If both conditions are satisfied, f[i][j] becomes True, signaling that it's possible to satisfy the subset of orders j using integers up to i. The while loop uses the bit manipulation trick k = (k - 1) & j to iterate through all non-empty subsets of j.

The last step is to check f[-1][-1], which tells us whether all the orders can be satisfied using all available unique numbers in nums. If f[-1][-1] is True, the solution returns true, indicating that it is indeed possible to distribute nums according to the order quantities in quantity.

Example Walkthrough

Let's take a small example to illustrate the solution approach.

Assume nums = [1, 2, 3, 4] and quantity = [2, 2]. The array nums consists of integers which have at most 2 different quantities: 2 of 1 and 2 of 2. The quantity array contains two customer order quantities: the first customer needs 2 integers and the second customer also needs 2 integers.

Firstly, we calculate all possible sums of quantity using bit manipulation. Here the possible sums are 0 (no customers), 2 (either customer), and 4 (both customers):

  • Subset bitmask 00 represents no customers, so sum s[0] is 0.
  • Subset bitmask 01 represents the first customer, so sum s[1] is 2.
  • Subset bitmask 10 represents the second customer, so sum s[2] is 2.
  • Subset bitmask 11 represents both customers, so sum s[3] is 4.

Then, we count how many times each number exists in nums:

  • Number 1 appears 1 time.
  • Number 2 appears 1 time.
  • Number 3 appears 1 time.
  • Number 4 appears 1 time.

The counter for nums shows each unique integer occurs just once, so our arr list contains [1,1,1,1].

The dynamic programming (DP) table f will have dimensions [4][1 << 2] (since we have 4 unique integers in nums and 2 customers), which becomes [4][4]. All values in f are initialized to False except f[i][0] for each row i, which is set to True.

Now, we loop through each x in arr (each being 1 in our example) and update the DP table f. We check if the current integer x can fulfill some combination of orders represented by j. We iterate over all non-empty subsets k of j. For our example, there aren't any integers in arr that can fulfill a sum of 2 or 4. However, here's how the DP table updating logic would look like if we had an integer x that could:

  • For x able to satisfy a sum of 2, f[i][01 or 10] would be set to True.
  • For x able to satisfy a sum of 4 as well, f[i][11] would be set to True.

In our hypothetical situation, if we found a large enough x in arr, and after iterating through the nested loops, we could possibly have the DP table f showing f[i][11] = True, indicating we can satisfy both customers. But since in our actual case x is 1 and cannot satisfy either customer's quantity demand of 2, the final state f[-1][-1] stays False.

Thus, the return value for our example will be False, indicating that it's not possible to distribute the numbers in nums to satisfy the quantities in quantity.

In summary, our example input nums = [1, 2, 3, 4] and quantity = [2, 2] does not satisfy the conditions for the customers’ orders since no integer in nums is available in sufficient quantity to fulfill a quantity of 2.

Python Solution

1from collections import Counter
2
3class Solution:
4    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
5        # The number of customers
6        num_customers = len(quantity)
7      
8        # Precompute the sums of all subsets of 'quantity'
9        subset_sums = [0] * (1 << num_customers)
10        for i in range(1, 1 << num_customers):
11            for j in range(num_customers):
12                if i >> j & 1:
13                    subset_sums[i] = subset_sums[i ^ (1 << j)] + quantity[j]
14                    break
15      
16        # Counts of each distinct number in 'nums'
17        count = Counter(nums)
18        counts = list(count.values())
19        num_counts = len(counts)
20      
21        # Dynamic programming table
22        # f[i][j] represents whether the first i+1 distinct numbers can fulfill
23        # the orders represented by binary state j
24        dp_table = [[False] * (1 << num_customers) for _ in range(num_counts)]
25        for i in range(num_counts):
26            dp_table[i][0] = True  # Base case: No customers means no quantities to fulfill
27      
28        # Iterate through each distinct count of numbers
29        for i, count in enumerate(counts):
30            # Iterate through all subsets of customers
31            for j in range(1, 1 << num_customers):
32                # If there was a previous count that satisfied the same set of customers
33                if i and dp_table[i - 1][j]:
34                    dp_table[i][j] = True
35                    continue
36                subset = j
37                # Iterate through subsets of the current subset
38                while subset:
39                    # Check if previous numbers can fulfill orders not served by the current number
40                    can_fulfill_previous = (j == subset) if i == 0 else dp_table[i - 1][j ^ subset]
41                    # If current count can serve this subset
42                    can_fulfill_current = subset_sums[subset] <= count
43                    # If both conditions are true, set dp_table to True
44                    if can_fulfill_previous and can_fulfill_current:
45                        dp_table[i][j] = True
46                        break
47                    subset = (subset - 1) & j
48      
49        # Return the answer for the last count and all customers
50        return dp_table[-1][-1]
51

Java Solution

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5
6    public boolean canDistribute(int[] nums, int[] quantity) {
7        // Calculate the length of the 'quantity' array
8        int quantityLength = quantity.length;
9        // Subset sum array to store the sum of quantities of each subset
10        int[] subsetSums = new int[1 << quantityLength];
11      
12        // Fill the 'subsetSums' array with the sum of subsets of 'quantity'
13        for (int i = 1; i < 1 << quantityLength; ++i) {
14            for (int j = 0; j < quantityLength; ++j) {
15                if ((i >> j & 1) != 0) {
16                    subsetSums[i] = subsetSums[i ^ (1 << j)] + quantity[j];
17                    break;
18                }
19            }
20        }
21
22        // Count the frequency of each number in 'nums'
23        Map<Integer, Integer> frequencyCount = new HashMap<>(50);
24        for (int number : nums) {
25            frequencyCount.merge(number, 1, Integer::sum);
26        }
27        // Store the count of unique numbers in 'nums'
28        int uniqueNumCount = frequencyCount.size();
29        int[] frequencyArray = new int[uniqueNumCount];
30        int index = 0;
31        for (int freq : frequencyCount.values()) {
32            frequencyArray[index++] = freq;
33        }
34
35        // Dynamic programming array to determine if a subset can be distributed
36        boolean[][] dp = new boolean[uniqueNumCount][1 << quantityLength];
37        // Initial condition: It is always possible to distribute no quantity
38        for (index = 0; index < uniqueNumCount; ++index) {
39            dp[index][0] = true;
40        }
41
42        for (index = 0; index < uniqueNumCount; ++index) {
43            for (int subsetMask = 1; subsetMask < 1 << quantityLength; ++subsetMask) {
44                if (index > 0 && dp[index - 1][subsetMask]) {
45                    dp[index][subsetMask] = true;
46                    continue;
47                }
48                for (int subMask = subsetMask; subMask > 0; subMask = (subMask - 1) & subsetMask) {
49                    boolean canDistributePrev = index == 0 ? subsetMask == subMask : dp[index - 1][subsetMask ^ subMask];
50                    boolean hasEnoughQuantity = subsetSums[subMask] <= frequencyArray[index];
51                    if (canDistributePrev && hasEnoughQuantity) {
52                        dp[index][subsetMask] = true;
53                        break;
54                    }
55                }
56            }
57        }
58        // Check if it is possible to distribute the entire 'quantity'
59        return dp[uniqueNumCount - 1][(1 << quantityLength) - 1];
60    }
61}
62

C++ Solution

1#include <vector>
2#include <unordered_map>
3#include <cstring>
4
5class Solution {
6public:
7    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
8        // Calculate the size of the quantity vector 
9        int quantitySize = quantity.size();
10        // Initialize the subset sum array with 2^quantitySize elements.
11        vector<int> subsetSums(1 << quantitySize, 0);
12
13        // Pre-compute the sum of each subset of the quantities.
14        for (int subsetMask = 1; subsetMask < (1 << quantitySize); ++subsetMask) {
15            for (int j = 0; j < quantitySize; ++j) {
16                if (subsetMask & (1 << j)) {
17                    subsetSums[subsetMask] = subsetSums[subsetMask ^ (1 << j)] + quantity[j];
18                    break;
19                }
20            }
21        }
22
23        // Count the occurrence of each unique number in the nums array.
24        unordered_map<int, int> countMap;
25        for (int x : nums) {
26            ++countMap[x];
27        }
28        // The number of unique numbers in nums.
29        int uniqueNumsCount = countMap.size();
30
31        // Create an array with the count of each unique number.
32        vector<int> counts;
33        for (auto& kv : countMap) {
34            counts.push_back(kv.second);
35        }
36
37        // Initialize a DP table to determine if a certain combination of numbers can distribute a certain combination of quantities.
38        vector<vector<bool>> dp(uniqueNumsCount, vector<bool>(1 << quantitySize, false));
39
40        // Base case: it's always possible to distribute nothing (empty subset).
41        for (int i = 0; i < uniqueNumsCount; ++i) {
42            dp[i][0] = true;
43        }
44
45        // Iterate over each unique number.
46        for (int i = 0; i < uniqueNumsCount; ++i) {
47            // Try every combination of quantities.
48            for (int subsetMask = 1; subsetMask < (1 << quantitySize); ++subsetMask) {
49                if (i > 0 && dp[i - 1][subsetMask]) {
50                    // If the previous number can already satisfy this combination, no need to check further.
51                    dp[i][subsetMask] = true;
52                    continue;
53                }
54                // Iterate through all submasks of the subsetMask.
55                for (int k = subsetMask; k; k = (k - 1) & subsetMask) {
56                    // Check if the combination of quantities corresponding to the submask k can be distributed by the current or previous numbers.
57                    bool canPreviousDistribute = (i == 0) ? (subsetMask == k) : dp[i - 1][subsetMask ^ k];
58                    bool canCurrentDistribute = subsetSums[k] <= counts[i];
59                    if (canPreviousDistribute && canCurrentDistribute) {
60                        // If both conditions are satisfied, mark this combination as possible.
61                        dp[i][subsetMask] = true;
62                        break;
63                    }
64                }
65            }
66        }
67        // Return true if all quantities can be distributed by all unique numbers; else return false.
68        return dp[uniqueNumsCount - 1][(1 << quantitySize) - 1];
69    }
70};
71

Typescript Solution

1function canDistribute(nums: number[], quantities: number[]): boolean {
2  // Define the length of the quantity array.
3  const quantityLength: number = quantities.length;
4  // Create an array to hold the sum of certain combinations of quantities.
5  const sums: number[] = new Array(1 << quantityLength).fill(0);
6  // Calculate the sum for each subset of quantities.
7  for (let i = 1; i < 1 << quantityLength; ++i) {
8    for (let j = 0; j < quantityLength; ++j) {
9      if ((i >> j) & 1) {
10        sums[i] = sums[i ^ (1 << j)] + quantities[j];
11        break;
12      }
13    }
14  }
15  // Count the occurrences of each unique number in the nums array.
16  const countMap: Map<number, number> = new Map();
17  for (const num of nums) {
18    countMap.set(num, (countMap.get(num) || 0) + 1);
19  }
20  // Determine the number of unique numbers.
21  const uniqueNumCount: number = countMap.size;
22  // Convert the map to an array of counts.
23  const countsArray: number[] = Array.from(countMap.values());
24  // Create a 2D array for dynamic programming.
25  const dp: boolean[][] = new Array(uniqueNumCount).fill(false).map(() =>
26    new Array(1 << quantityLength).fill(false)
27  );
28
29  // Set the base case for the dynamic programming solution.
30  for (let i = 0; i < uniqueNumCount; ++i) {
31    dp[i][0] = true;
32  }
33
34  // Iterate over each unique number and each subset of quantities.
35  for (let i = 0; i < uniqueNumCount; ++i) {
36    for (let j = 0; j < 1 << quantityLength; ++j) {
37      // If the current subset can be achieved without the current number, set the dp state to true.
38      if (i > 0 && dp[i - 1][j]) {
39        dp[i][j] = true;
40        continue;
41      }
42      // Check if there exists a subset of the current subset that can be fulfilled with the current number's count.
43      for (let subset = j; subset > 0; subset = (subset - 1) & j) {
44        const validSubset = (i == 0 && j == subset) || (i > 0 && dp[i - 1][j ^ subset]);
45        const enoughQuantity = sums[subset] <= countsArray[i];
46        if (validSubset && enoughQuantity) {
47          dp[i][j] = true;
48          break;
49        }
50      }
51    }
52  }
53
54  // Return whether the entire set of quantities can be distributed.
55  return dp[uniqueNumCount - 1][(1 << quantityLength) - 1];
56}
57

Time and Space Complexity

The given code is an implementation of a solution to the problem of checking whether it is possible to distribute nums into quantity. Let's analyze the time and space complexity of the provided code:

Time Complexity

The time complexity can be analyzed as follows:

  • There are two nested loops at the beginning which build an array s of size 2^m where m is the length of quantity. This takes O(m * 2^m) time since for every subset, it calculates the sum of quantities in that subset.
  • The cnt = Counter(nums) operation has a time complexity of O(n) where n is the number of elements in nums.
  • The double nested loops that build the f table iterate over every element in arr (which is at most n) and over every possible combination of quantity (2^m possibilities), making it O(n * 2^m).
  • Inside the innermost loop, there is another while-loop that can iterate up to m times for each bit-set in k.

Putting this all together, the dominant part of the time complexity is the double nested loops, leading to an overall time complexity of O(n * 2^m + m * 2^m), which simplifies to O((n + m) * 2^m).

Space Complexity

The space complexity is determined by:

  • The extra array s, which has a space complexity of O(2^m).
  • The cnt object, which in the worst case, contains as many keys as there are unique elements in nums. In the worst case, this is O(n).
  • The f table, which is a 2D table of n rows and 2^m columns, thus having a space complexity of O(n * 2^m).

Therefore, the total space complexity is dominated by the f table, giving us a space complexity of O(n * 2^m).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫