Question

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 1: State Compression Dynamic Programming + Subset Enumeration

First, we count the occurrence of each number in the array nums, and record it in the hash table cnt. Then we store the values in the hash table into the array arr. We denote the length of the array arr as n.

Note that the length of the array quantity does not exceed 10, so we can use a binary number to represent a subset of quantity. That is, the number j represents a subset of quantity, where the i-th bit of the binary representation of j is 1 means the i-th number in quantity is selected, and 0 means the i-th number is not selected.

We can preprocess an array s, where s[j] represents the sum of all numbers in the subset j of quantity.

Next, we define f[i][j] to represent whether the numbers in arr[0,..i-1] can be successfully allocated to the subset j of quantity, where i ranges from [0,..n-1], and j ranges from [0,2^m-1], where m is the length of quantity.

Considering f[i][j], if there exists a subset k in j such that s[k] <= arr[i], and f[i-1][j XOR k] is true, then f[i][j] is true, otherwise f[i][j] is false.

The answer is f[n-1][2^m-1].

The time complexity is O(n * 3^m), and the space complexity is O(n * 2^m). Here, n is the number of different integers in the array nums, and m is the length of the array quantity.

class Solution:
  def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
    m = len(quantity)
    s = [0] * (1 << m)
    for i in range(1, 1 << m):
      for j in range(m):
        if i >> j & 1:
          s[i] = s[i ^ (1 << j)] + quantity[j]
          break
    cnt = Counter(nums)
    arr = list(cnt.values())
    n = len(arr)
    f = [[False] * (1 << m) for _ in range(n)]
    for i in range(n):
      f[i][0] = True
    for i, x in enumerate(arr):
      for j in range(1, 1 << m):
        if i and f[i - 1][j]:
          f[i][j] = True
          continue
        k = j
        while k:
          ok1 = j == k if i == 0 else f[i - 1][j ^ k]
          ok2 = s[k] <= x
          if ok1 and ok2:
            f[i][j] = True
            break
          k = (k - 1) & j
    return f[-1][-1]

class Solution {
  public boolean canDistribute(int[] nums, int[] quantity) {
    int m = quantity.length;
    int[] s = new int[1 << m];
    for (int i = 1; i < 1 << m; ++i) {
      for (int j = 0; j < m; ++j) {
        if ((i >> j & 1) != 0) {
          s[i] = s[i ^ (1 << j)] + quantity[j];
          break;
        }
      }
    }
    Map<Integer, Integer> cnt = new HashMap<>(50);
    for (int x : nums) {
      cnt.merge(x, 1, Integer::sum);
    }
    int n = cnt.size();
    int[] arr = new int[n];
    int i = 0;
    for (int x : cnt.values()) {
      arr[i++] = x;
    }
    boolean[][] f = new boolean[n][1 << m];
    for (i = 0; i < n; ++i) {
      f[i][0] = true;
    }
    for (i = 0; i < n; ++i) {
      for (int j = 1; j < 1 << m; ++j) {
        if (i > 0 && f[i - 1][j]) {
          f[i][j] = true;
          continue;
        }
        for (int k = j; k > 0; k = (k - 1) & j) {
          boolean ok1 = i == 0 ? j == k : f[i - 1][j ^ k];
          boolean ok2 = s[k] <= arr[i];
          if (ok1 && ok2) {
            f[i][j] = true;
            break;
          }
        }
      }
    }
    return f[n - 1][(1 << m) - 1];
  }
}

class Solution {
public:
  bool canDistribute(vector<int>& nums, vector<int>& quantity) {
    int m = quantity.size();
    int s[1 << m];
    memset(s, 0, sizeof(s));
    for (int i = 1; i < 1 << m; ++i) {
      for (int j = 0; j < m; ++j) {
        if (i >> j & 1) {
          s[i] = s[i ^ (1 << j)] + quantity[j];
          break;
        }
      }
    }
    unordered_map<int, int> cnt;
    for (int& x : nums) {
      ++cnt[x];
    }
    int n = cnt.size();
    vector<int> arr;
    for (auto& [_, x] : cnt) {
      arr.push_back(x);
    }
    bool f[n][1 << m];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; ++i) {
      f[i][0] = true;
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 1; j < 1 << m; ++j) {
        if (i && f[i - 1][j]) {
          f[i][j] = true;
          continue;
        }
        for (int k = j; k; k = (k - 1) & j) {
          bool ok1 = i == 0 ? j == k : f[i - 1][j ^ k];
          bool ok2 = s[k] <= arr[i];
          if (ok1 && ok2) {
            f[i][j] = true;
            break;
          }
        }
      }
    }
    return f[n - 1][(1 << m) - 1];
  }
};

func canDistribute(nums []int, quantity []int) bool {
  m := len(quantity)
  s := make([]int, 1<<m)
  for i := 1; i < 1<<m; i++ {
    for j := 0; j < m; j++ {
      if i>>j&1 == 1 {
        s[i] = s[i^(1<<j)] + quantity[j]
        break
      }
    }
  }
  cnt := map[int]int{}
  for _, x := range nums {
    cnt[x]++
  }
  n := len(cnt)
  arr := make([]int, 0, n)
  for _, x := range cnt {
    arr = append(arr, x)
  }
  f := make([][]bool, n)
  for i := range f {
    f[i] = make([]bool, 1<<m)
    f[i][0] = true
  }
  for i := 0; i < n; i++ {
    for j := 0; j < 1<<m; j++ {
      if i > 0 && f[i-1][j] {
        f[i][j] = true
        continue
      }
      for k := j; k > 0; k = (k - 1) & j {
        ok1 := (i == 0 && j == k) || (i > 0 && f[i-1][j-k])
        ok2 := s[k] <= arr[i]
        if ok1 && ok2 {
          f[i][j] = true
          break
        }
      }
    }
  }
  return f[n-1][(1<<m)-1]
}

function canDistribute(nums: number[], quantity: number[]): boolean {
  const m = quantity.length;
  const s: number[] = new Array(1 << m).fill(0);
  for (let i = 1; i < 1 << m; ++i) {
    for (let j = 0; j < m; ++j) {
      if ((i >> j) & 1) {
        s[i] = s[i ^ (1 << j)] + quantity[j];
        break;
      }
    }
  }
  const cnt: Map<number, number> = new Map();
  for (const x of nums) {
    cnt.set(x, (cnt.get(x) || 0) + 1);
  }
  const n = cnt.size;
  const arr: number[] = [];
  for (const [_, v] of cnt) {
    arr.push(v);
  }
  const f: boolean[][] = new Array(n).fill(false).map(() => new Array(1 << m).fill(false));
  for (let i = 0; i < n; ++i) {
    f[i][0] = true;
  }
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < 1 << m; ++j) {
      if (i > 0 && f[i - 1][j]) {
        f[i][j] = true;
        continue;
      }
      for (let k = j; k > 0; k = (k - 1) & j) {
        const ok1: boolean = (i == 0 && j == k) || (i > 0 && f[i - 1][j ^ k]);
        const ok2: boolean = s[k] <= arr[i];
        if (ok1 && ok2) {
          f[i][j] = true;
          break;
        }
      }
    }
  }
  return f[n - 1][(1 << m) - 1];
}