1351. Distribute Repeating Integers (Bitmask DP)

You have an array of integers and a list of customer orders, where quantity[i] is how many items customer i wants. Every customer must receive exactly quantity[i] copies of one single value, and different customers may take the same value only if enough copies exist. Determine whether all customers can be satisfied.

Input: A JSON object {"nums": [<integers>], "quantity": [<order sizes>]}.

Output: Return true if every customer can be served, otherwise false.

Examples

Input: {"nums":[1,2,3,4],"quantity":[2]}
Output: false
Explanation: No value appears twice, so the order cannot be filled -> false.

Input: {"nums":[1,1,2,2],"quantity":[2,2]}
Output: true
Explanation: Each customer takes one value entirely -> true.

Constraints

• 1 <= len(nums) <= 10^5
• 1 <= len(quantity) <= 10
• 1 <= quantity[i] <= 10^5

Asked by