We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count of Sub-Multisets With Bounded Sum

Number: 3091

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of non-negative integers and two integers l and r, count the number of sub-multisets (i.e. unordered selections where each number x can be taken 0 to its frequency times) such that the sum of the selected elements is within the inclusive range [l, r]. The answer should be returned modulo 10^9 + 7.

Key Insights

  • The problem asks for counting multisets, which is equivalent to choosing 0 up to occurrence_count of each unique number.
  • Due to potential duplicates, it’s more efficient to group numbers by their value.
  • The sum of the array is at most 20000, allowing the use of a DP array with dimension equal to the maximum possible sum.
  • Special handling for zeros is important since choosing zeros does not affect the sum but increases the number of possible multisets multiplicatively.
  • The solution uses dynamic programming by updating the ways to form each sum when considering a new group of identical numbers.

Space and Time Complexity

Time Complexity: O(U * total_sum * max_frequency) in the worst-case scenario, where U is the number of distinct non-zero numbers.
Space Complexity: O(total_sum), where total_sum is the sum of the numbers (at most 20000).

Solution

We solve the problem using dynamic programming. First, we group the numbers by their value. We treat the number 0 as a special case: since adding a 0 does not change the sum, if there are f zeros, they contribute a multiplicative factor of (f+1) (as you can choose between 0 to f zeros). For each distinct non-zero number, we update a DP array that tracks the number of ways to obtain a certain sum. For each group with value x and frequency count, for each possible sum already achievable, we add ways by taking 0, 1, 2, ... up to count occurrences of that number (ensuring the sum does not exceed the total possible sum). Finally, we take the sum of DP values for sums in the target range [l, r] and multiply by the factor from zeros. All operations are performed modulo 10^9+7.

Code Solutions

MOD = 10**9 + 7

def countSubMultisets(nums, l, r):
    total_sum = sum(nums)
    
    # Count zeros separately because they do not affect the sum.
    zeros = nums.count(0)
    non_zero_nums = [num for num in nums if num != 0]
    
    # Group the non-zero numbers by value.
    freq = {}
    for num in non_zero_nums:
        freq[num] = freq.get(num, 0) + 1

    # dp[s] = number of ways to obtain sum s using groups processed so far.
    dp = [0] * (total_sum + 1)
    dp[0] = 1  # one way (empty set)
    
    # Process each distinct non-zero number.
    for num, count in freq.items():
        new_dp = [0] * (total_sum + 1)
        for s in range(total_sum + 1):
            # For every count of the current number from 0 up to count.
            if dp[s]:
                for j in range(count + 1):
                    ns = s + j * num
                    if ns > total_sum:
                        break
                    new_dp[ns] = (new_dp[ns] + dp[s]) % MOD
        dp = new_dp

    # Sum counts for sums in the range [l, r].
    total_count = 0
    # The maximum sum achievable with non-zero numbers is total_sum (zeros do not add to the sum)
    for s in range(l, min(r, total_sum) + 1):
        total_count = (total_count + dp[s]) % MOD
    
    # Account for the zeros: each subset from non-zero part can be combined with any selection of zeros.
    # There are (zeros + 1) choices for the zeros.
    total_count = (total_count * pow(zeros + 1, 1, MOD)) % MOD
    return total_count

# Example usage:
print(countSubMultisets([1,2,2,3], 6, 6))  # Expected 1
print(countSubMultisets([2,1,4,2,7], 1, 5))  # Expected 7
print(countSubMultisets([1,2,1,3,5,2], 3, 5))  # Expected 9
← Back to All Questions