1655. Distribute Repeating Integers

Description

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.

 

Example 1:

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

Example 2:

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:

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

 

Constraints:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= 1000
• m == quantity.length
• 1 <= m <= 10
• 1 <= quantity[i] <= 105
• There are at most 50 unique values in nums.

 

Solutions

Solution: Dynamic Programming + Bit Manipulation

• Time complexity: O(50*3^m)
• Space complexity: O(50*2^m)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number[]} quantity
 * @return {boolean}
 */
const canDistribute = function (nums, quantity) {
  const m = quantity.length;
  const numMap = new Map();
  const memo = new Map();
  const totalMask = (1 << m) - 1;

  for (const num of nums) {
    const count = numMap.get(num) ?? 0;

    numMap.set(num, count + 1);
  }
  const counts = [...numMap.values()];
  const sums = Array.from({ length: 1 << m }, () => 0);

  for (let mask = 1; mask <= totalMask; mask++) {
    for (let index = 0; index < m; index++) {
      if (mask & (1 << index)) {
        sums[mask] += quantity[index];
      }
    }
  }

  const distributeInteger = (index, mask) => {
    if (mask === 0) return true;
    if (index >= counts.length) return false;
    const key = `${index},${mask}`;

    if (memo.has(key)) return memo.get(key);
    if (distributeInteger(index + 1, mask)) {
      memo.set(key, true);

      return true;
    }
    let subMask = mask;

    while (subMask) {
      if (sums[subMask] <= counts[index] && distributeInteger(index + 1, mask ^ subMask)) {
        memo.set(key, true);

        return true;
      }

      subMask = (subMask - 1) & mask;
    }

    memo.set(key, false);

    return false;
  };

  return distributeInteger(0, totalMask);
};