Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Distribute Repeating Integers

Problem (restated)

Frequencies of values in nums, plus m ≤ 10 customers each wanting quantity[i] copies of one value. Several customers may share a value if the pile is large enough. Can every customer be satisfied?

Intuition

Compress nums to frequency piles. The customers are the small set: 2^m masks. For each pile, assign it some still-unsatisfied submask whose quantity sum fits in that frequency.

Approaches

Submask assignment DP

Unverified

Time O(k * 3^m)Space O(2^m)

Idea. sums[mask] = total demand of those customers. ok[mask] = can satisfy that set with piles seen so far. For each frequency f, every reachable mask, every submask of the complement: if sums[sub] ≤ f, mark mask | sub.

Walkthrough. [1,2,3,4], [2] → false (no pile of 2). [1,2,3,3], [2] → true. [1,1,2,2,3,3,4,4,4,4], [2,3] → true (4’s take 3, another pile takes 2).

Trade-offs. Submask enumeration is 3^m per pile, not 4^m. Dual-tagged MITM: you could split customers in half and match assignments; with m≤10 the full mask is enough.

Solution

export function canDistribute(nums: number[], quantity: number[]): boolean {
  const cnt = new Map<number, number>();
  for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
  const freqs = [...cnt.values()];
  const m = quantity.length;
  const full = (1 << m) - 1;
  const sums = new Array<number>(1 << m).fill(0);
  for (let mask = 1; mask <= full; mask++) {
    let s = 0;
    for (let i = 0; i < m; i++) if (mask & (1 << i)) s += quantity[i]!;
    sums[mask] = s;
  }
  let ok = new Array<boolean>(1 << m).fill(false);
  ok[0] = true;
  for (const f of freqs) {
    const nxt = ok.slice();
    for (let mask = 0; mask <= full; mask++) {
      if (!ok[mask]) continue;
      const need = full ^ mask;
      let sub = need;
      while (true) {
        if (sums[sub]! <= f) nxt[mask | sub] = true;
        if (sub === 0) break;
        sub = (sub - 1) & need;
      }
    }
    ok = nxt;
    if (ok[full]) return true;
  }
  return ok[full]!;
}

export function canDistribute(nums: number[], quantity: number[]): boolean {
  const cnt = new Map<number, number>();
  for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
  const freqs = [...cnt.values()];
  const m = quantity.length;
  const full = (1 << m) - 1;
  const sums = new Array<number>(1 << m).fill(0);
  for (let mask = 1; mask <= full; mask++) {
    let s = 0;
    for (let i = 0; i < m; i++) if (mask & (1 << i)) s += quantity[i]!;
    sums[mask] = s;
  }
  let ok = new Array<boolean>(1 << m).fill(false);
  ok[0] = true;
  for (const f of freqs) {
    const nxt = ok.slice();
    for (let mask = 0; mask <= full; mask++) {
      if (!ok[mask]) continue;
      const need = full ^ mask;
      let sub = need;
      while (true) {
        if (sums[sub]! <= f) nxt[mask | sub] = true;
        if (sub === 0) break;
        sub = (sub - 1) & need;
      }
    }
    ok = nxt;
    if (ok[full]) return true;
  }
  return ok[full]!;
}

Template connection

Assignment / partition bitmask DP: each pile claims a submask of remaining customers. MITM is the same split when m is larger.

Reflection

sums[mask] is the total demand of those customers. For each frequency f and each reached mask, mark mask | sub when sub is a submask of the complement and sums[sub] <= f.
One frequency bucket is given to one group of customers. The same bucket is not used twice.
If no assignment fits the demands, the answer is false. The customer count is small, so the mask is 2**m. The empty customer set is true.