Skip to content

1655. Distribute Repeating Integers 👍

  • Time: $O(50 \cdot 3^m)$
  • Space: $O(50 \cdot 2^m)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
 public:
  bool canDistribute(vector<int>& nums, vector<int>& quantity) {
    // validDistribution[i][j] := true if it's possible to distribute the i-th
    // freq into a subset of quantity represented by the bitmask j
    const vector<int> freqs = getFreqs(nums);
    const vector<vector<bool>> validDistribution =
        getValidDistribuition(freqs, quantity);
    const int n = freqs.size();
    const int m = quantity.size();
    const int maxMask = 1 << m;
    // dp[i][j] := true if it's possible to distribute freqs[i..n), where j is
    // the bitmask of the selected quantity
    vector<vector<bool>> dp(n + 1, vector<bool>(maxMask));
    dp[n][maxMask - 1] = true;

    for (int i = n - 1; i >= 0; --i)
      for (int mask = 0; mask < maxMask; ++mask) {
        dp[i][mask] = dp[i + 1][mask];
        const int availableMask = ~mask & (maxMask - 1);
        for (int submask = availableMask; submask > 0;
             submask = (submask - 1) & availableMask)
          if (validDistribution[i][submask])
            dp[i][mask] = dp[i][mask] || dp[i + 1][mask | submask];
      }

    return dp[0][0];
  }

 private:
  vector<int> getFreqs(const vector<int>& nums) {
    vector<int> freqs;
    unordered_map<int, int> count;
    for (const int num : nums)
      ++count[num];
    for (const auto& [_, freq] : count)
      freqs.push_back(freq);
    return freqs;
  }

  vector<vector<bool>> getValidDistribuition(const vector<int>& freqs,
                                             const vector<int>& quantity) {
    const int maxMask = 1 << quantity.size();
    vector<vector<bool>> validDistribution(freqs.size(), vector<bool>(maxMask));
    for (int i = 0; i < freqs.size(); ++i)
      for (int mask = 0; mask < maxMask; ++mask)
        if (freqs[i] >= getQuantitySum(quantity, mask))
          validDistribution[i][mask] = true;
    return validDistribution;
  }

  // Returns the sum of the selected quantity represented by `mask`.
  int getQuantitySum(const vector<int>& quantity, int mask) {
    int sum = 0;
    for (int i = 0; i < quantity.size(); ++i)
      if (mask >> i & 1)
        sum += quantity[i];
    return sum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
  public boolean canDistribute(int[] nums, int[] quantity) {
    List<Integer> freqs = getFreqs(nums);
    // validDistribution[i][j] := true if it's possible to distribute the i-th
    // freq into a subset of quantity represented by the bitmask j
    boolean[][] validDistribution = getValidDistribution(freqs, quantity);
    final int n = freqs.size();
    final int m = quantity.length;
    final int maxMask = 1 << m;
    // dp[i][j] := true if it's possible to distribute freqs[i..n), where j is
    // the bitmask of the selected quantity
    boolean[][] dp = new boolean[n + 1][maxMask];
    dp[n][maxMask - 1] = true;

    for (int i = n - 1; i >= 0; --i)
      for (int mask = 0; mask < maxMask; ++mask) {
        dp[i][mask] = dp[i + 1][mask];
        final int availableMask = ~mask & (maxMask - 1);
        for (int submask = availableMask; submask > 0; submask = (submask - 1) & availableMask)
          if (validDistribution[i][submask])
            dp[i][mask] = dp[i][mask] || dp[i + 1][mask | submask];
      }

    return dp[0][0];
  }

  private List<Integer> getFreqs(int[] nums) {
    List<Integer> freqs = new ArrayList<>();
    Map<Integer, Integer> count = new HashMap<>();
    for (final int num : nums)
      count.merge(num, 1, Integer::sum);
    return new ArrayList<>(count.values());
  }

  boolean[][] getValidDistribution(List<Integer> freqs, int[] quantity) {
    final int maxMask = 1 << quantity.length;
    boolean[][] validDistribution = new boolean[freqs.size()][maxMask];
    for (int i = 0; i < freqs.size(); ++i)
      for (int mask = 0; mask < maxMask; ++mask)
        if (freqs.get(i) >= getQuantitySum(quantity, mask))
          validDistribution[i][mask] = true;
    return validDistribution;
  }

  // Returns the sum of the selected quantity represented by `mask`.
  int getQuantitySum(int[] quantity, int mask) {
    int sum = 0;
    for (int i = 0; i < quantity.length; ++i)
      if ((mask >> i & 1) == 1)
        sum += quantity[i];
    return sum;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
  def canDistribute(self, nums: list[int], quantity: list[int]) -> bool:
    freqs = list(collections.Counter(nums).values())
    # validDistribution[i][j] := True if it's possible to distribute the i-th
    # freq into a subset of quantity represented by the bitmask j
    validDistribution = self._getValidDistribution(freqs, quantity)
    n = len(freqs)
    m = len(quantity)
    maxMask = 1 << m
    # dp[i][j] := true if it's possible to distribute freqs[i..n), where j is
    # the bitmask of the selected quantity
    dp = [[False] * maxMask for _ in range(n + 1)]
    dp[n][maxMask - 1] = True

    for i in range(n - 1, -1, -1):
      for mask in range(maxMask):
        dp[i][mask] = dp[i + 1][mask]
        availableMask = ~mask & (maxMask - 1)
        submask = availableMask
        while submask > 0:
          if validDistribution[i][submask]:
            dp[i][mask] = dp[i][mask] or dp[i + 1][mask | submask]
          submask = (submask - 1) & availableMask

    return dp[0][0]

  def _getValidDistribution(self, freqs: list[int],
                            quantity: list[int]) -> list[list[bool]]:
    maxMask = 1 << len(quantity)
    validDistribution = [[False] * maxMask for _ in range(len(freqs))]
    for i, freq in enumerate(freqs):
      for mask in range(maxMask):
        if freq >= self._getQuantitySum(quantity, mask):
          validDistribution[i][mask] = True
    return validDistribution

  def _getQuantitySum(self, quantity: list[int], mask: int) -> int:
    """Returns the sum of the selected quantity represented by `mask`."""
    return sum(q for i, q in enumerate(quantity) if mask >> i & 1)