Distribute Repeating Integers Solution in Python

Problem Description

Ah, the classic “Distribute Repeating Integers” problem! It’s like trying to share a pizza among your friends, but instead of slices, you have integers, and instead of friends, you have quantities that need to be satisfied. Imagine you have a bag of candies (or integers, in this case) and a group of friends who all want a specific number of candies. The catch? Some candies are identical, and you need to figure out if you can distribute them in such a way that everyone gets their desired amount.

So, if you have 10 identical candies and your friends want 3, 3, and 4 candies respectively, you might find yourself in a sticky situation. Can you make it work? Or will you end up with a bunch of disappointed friends and a sad pizza (or candy) party?

Code Solution


class Solution:
    def canDistribute(self, nums: list[int], quantity: list[int]) -> bool:
        freqs = list(collections.Counter(nums).values())
        validDistribution = self._getValidDistribution(freqs, quantity)
        n = len(freqs)
        m = len(quantity)
        maxMask = 1 << m
        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)

Approach Explanation

The code uses a dynamic programming approach to determine if the integers can be distributed according to the specified quantities. It first calculates the frequency of each integer and then checks if these frequencies can satisfy 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 based on the valid combinations.

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 at a birthday party with a piñata filled with candies. Each child (friend) has a specific number of candies they want. You need to figure out if you can distribute the candies from the piñata in such a way that every child leaves happy. If you can manage to do that, you’ll be the hero of the party! If not, well, let’s just say you might want to avoid the angry mob of sugar-deprived children.

Navigation Links

If you’re interested in exploring solutions in other languages, check out the links below: