Distribute Repeating Integers Solution in C++

Explore More Solutions:

Problem Description

Ah, the classic dilemma of distributing repeating integers! Imagine you’re at a party, and you have a bag of candies (or maybe it’s just a bag of your hopes and dreams). You want to share these candies with your friends, but there’s a catch: each friend has a specific number of candies they want. Now, if you have a few candies that are the same, how do you distribute them without causing a riot?

In the LeetCode problem “Distribute Repeating Integers,” you are given an array of integers (the candies) and a list of quantities (the friends’ demands). Your task is to determine if it’s possible to distribute the candies such that each friend gets exactly what they want. If you can do it, you’re a hero; if not, well, you might want to consider a career in candy manufacturing instead.

Code Solution


class Solution {
 public:
  bool canDistribute(vector& nums, vector& quantity) {
    const vector freqs = getFreqs(nums);
    const vector> validDistribution =
        getValidDistribuition(freqs, quantity);
    const int n = freqs.size();
    const int m = quantity.size();
    const int maxMask = 1 << m;
    vector> dp(n + 1, vector(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 getFreqs(const vector& nums) {
    vector freqs;
    unordered_map count;
    for (const int num : nums)
      ++count[num];
    for (const auto& [_, freq] : count)
      freqs.push_back(freq);
    return freqs;
  }

  vector> getValidDistribuition(const vector& freqs,
                                             const vector& quantity) {
    const int maxMask = 1 << quantity.size();
    vector> validDistribution(freqs.size(), vector(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;
  }

  int getQuantitySum(const vector& quantity, int mask) {
    int sum = 0;
    for (int i = 0; i < quantity.size(); ++i)
      if (mask >> i & 1)
        sum += quantity[i];
    return sum;
  }
};

Approach Explanation

The solution employs a dynamic programming approach to determine if the distribution of integers is feasible. It first calculates the frequency of each integer in the input array. Then, it checks all possible distributions of these frequencies against the required quantities using bitmasking. The dp array keeps track of whether a certain distribution is possible, iterating through the frequencies and updating the possible distributions accordingly.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * 2^m)
Space Complexity	O(n * 2^m)

Real-World Example

Imagine you’re organizing a birthday party and you have a box of cupcakes. Each friend has a specific craving for a certain number of cupcakes. You need to figure out if you can satisfy everyone’s sweet tooth without running out of cupcakes. This problem mirrors the “Distribute Repeating Integers” challenge, where you must ensure that the available cupcakes (integers) can meet the demands (quantities) of your friends.