Distribute Repeating Integers

Distribute Repeating Integers

What is this problem about?

In the Distribute Repeating Integers coding problem, you have an array of integers and an array of quantities representing customer orders. Each customer $i$ wants quantity[i] of the same integer. You need to determine if it is possible to satisfy all customers using the available integers. For example, if a customer wants 3 of something, you must find an integer that appears at least 3 times in your collection.

Why is this asked in interviews?

Google uses this "Hard" problem to test your ability to optimize Backtracking using Bitmasks or Dynamic Programming. It evaluation how you handle a bin-packing-like problem where the items (orders) must be placed into bins (available integer counts). Since the number of customers is small (up to 10), it’s a perfect candidate for Bitmask DP.

Algorithmic pattern used

This problem is best solved using Dynamic Programming with Bitmasks.

1. Calculate the frequencies of all integers in the input. We only care about the counts, not the numbers themselves.
2. Let dp[i][mask] be a boolean indicating if we can satisfy the subset of customers represented by mask using the first i distinct integers.
3. For the i-th integer count $C$, and a mask, we can satisfy a sub-mask sub if the sum of quantities in sub is $\le C$.
4. dp[i][mask] = dp[i-1][mask] OR (dp[i-1][mask ^ sub] AND sum(sub) <= count[i]).

Example explanation

Counts: [5], Quantities: [2, 3].

1. dp[0][00] = true (empty subset).
2. Try satisfying customer 1 (mask 01, qty 2): $2 \le 5$. dp[1][01] = true.
3. Try satisfying customer 2 (mask 10, qty 3): $3 \le 5$. dp[1][10] = true.
4. Try satisfying both (mask 11, qty 2+3=5): $5 \le 5$. dp[1][11] = true. Result: true.

Common mistakes candidates make

• Naive Backtracking: Trying every integer for every customer without memoization, which is $O(N^M)$ and will time out.
• Sorting: Forgetting to sort the quantities in descending order to prune the search space earlier.
• Complexity: Not realizing that since there are only 10 customers, a bitmask of $2^{10}$ is very efficient.

Interview preparation tip

When you see a problem where you need to distribute resources to a small number of entities ($\le 15$), think Bitmask DP. It is the standard way to represent subsets and avoid redundant calculations in "matching" or "packing" problems.