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 i
th 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:
- Each
i
th customer should receive exactlyquantity[i]
number of integers. - All the integers a customer receives must be identical.
- 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.
Flowchart Walkthrough
First, let's analyze the problem using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- No: The problem does not revolve around nodes and edges typically seen in graph problems.
Need to solve for kth smallest/largest?
- No: The problem is about distributing integers and isn't focused on finding the kth smallest or largest element.
Involves Linked Lists?
- No: This problem does not involve manipulating or traversing linked lists.
Does the problem have small constraints?
- Yes: The constraints relate to the number of integers and the number of groups, which make it feasible for exploring all potential distributions.
Brute force / Backtracking?
- Yes: Given the small constraints and the need to explore possible distributions, brute force or backtracking is suitable for solving the problem by exploring each potential way to fulfill the group's requirements with the available integers.
Conclusion: Based on the analysis through the provided flowchart, a backtracking approach is suggested for solving LeetCode 1655, as it involves exploring various combinations to distribute integers across specified groups.
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:
- Generate all possible subsets of order quantities that can be fulfilled.
- 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. - 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. - 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. - 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.
Learn more about Dynamic Programming, Backtracking and Bitmask patterns.
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 tok
(or iff[i-1][j^k]
isTrue
for non-first integers), it means previous integers (up toi-1
) can already fulfill the other part of orders (j^k
). - If
s[k]
is less than or equal tox
, it meansx
can be used to fulfill the orders in subsetk
.
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 sums[0]
is0
. - Subset bitmask
01
represents the first customer, so sums[1]
is2
. - Subset bitmask
10
represents the second customer, so sums[2]
is2
. - Subset bitmask
11
represents both customers, so sums[3]
is4
.
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 of2
,f[i][01 or 10]
would be set toTrue
. - For
x
able to satisfy a sum of4
as well,f[i][11]
would be set toTrue
.
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
.
Solution Implementation
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
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
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
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 size2^m
wherem
is the length ofquantity
. This takesO(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 ofO(n)
wheren
is the number of elements innums
. - The double nested loops that build the
f
table iterate over every element inarr
(which is at mostn
) and over every possible combination ofquantity
(2^m
possibilities), making itO(n * 2^m)
. - Inside the innermost loop, there is another while-loop that can iterate up to
m
times for each bit-set ink
.
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 ofO(2^m)
. - The
cnt
object, which in the worst case, contains as many keys as there are unique elements innums
. In the worst case, this isO(n)
. - The
f
table, which is a 2D table ofn
rows and2^m
columns, thus having a space complexity ofO(n * 2^m)
.
Therefore, the total space complexity is dominated by the f
table, giving us a space complexity of O(n * 2^m)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.