Welcome to Subscribe On Youtube

2902. Count of Sub-Multisets With Bounded Sum

Description

You are given a 0-indexed array nums of non-negative integers, and two integers l and r.

Return the count of sub-multisets within nums where the sum of elements in each subset falls within the inclusive range of [l, r].

Since the answer may be large, return it modulo 109 + 7.

A sub-multiset is an unordered collection of elements of the array in which a given value x can occur 0, 1, ..., occ[x] times, where occ[x] is the number of occurrences of x in the array.

Note that:

  • Two sub-multisets are the same if sorting both sub-multisets results in identical multisets.
  • The sum of an empty multiset is 0.

 

Example 1:

Input: nums = [1,2,2,3], l = 6, r = 6
Output: 1
Explanation: The only subset of nums that has a sum of 6 is {1, 2, 3}.

Example 2:

Input: nums = [2,1,4,2,7], l = 1, r = 5
Output: 7
Explanation: The subsets of nums that have a sum within the range [1, 5] are {1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4}, and {1, 2, 2}.

Example 3:

Input: nums = [1,2,1,3,5,2], l = 3, r = 5
Output: 9
Explanation: The subsets of nums that have a sum within the range [3, 5] are {3}, {5}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {1, 1, 2}, {1, 1, 3}, and {1, 2, 2}.

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 0 <= nums[i] <= 2 * 104
  • Sum of nums does not exceed 2 * 104.
  • 0 <= l <= r <= 2 * 104

Solutions

  • class Solution:
        def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
            kMod = 1_000_000_007
            # dp[i] := # of submultisets of nums with sum i
            dp = [1] + [0] * r
            count = collections.Counter(nums)
            zeros = count.pop(0, 0)
    
            for num, freq in count.items():
                # stride[i] := dp[i] + dp[i - num] + dp[i - 2 * num] + ...
                stride = dp.copy()
                for i in range(num, r + 1):
                    stride[i] += stride[i - num]
                for i in range(r, 0, -1):
                    if i >= num * (freq + 1):
                        # dp[i] + dp[i - num] + dp[i - freq * num]
                        dp[i] = stride[i] - stride[i - num * (freq + 1)]
                    else:
                        dp[i] = stride[i]
    
            return (zeros + 1) * sum(dp[l : r + 1]) % kMod
    
    
  • 
    class Solution {
        static final int MOD = 1_000_000_007;
        public int countSubMultisets(List<Integer> nums, int l, int r) {
            Map<Integer, Integer> count = new HashMap<>();
            int total = 0;
            for (int num : nums) {
                total += num;
                if (num <= r) {
                    count.merge(num, 1, Integer::sum);
                }
            }
            if (total < l) {
                return 0;
            }
            r = Math.min(r, total);
            int[] dp = new int[r + 1];
            dp[0] = count.getOrDefault(0, 0) + 1;
            count.remove(Integer.valueOf(0));
            int sum = 0;
            for (Map.Entry<Integer, Integer> e : count.entrySet()) {
                int num = e.getKey();
                int c = e.getValue();
                sum = Math.min(sum + c * num, r);
                // prefix part
                // dp[i] = dp[i] + dp[i - num] + ... + dp[i - c*num] + dp[i-(c+1)*num] + ... + dp[i %
                // num]
                for (int i = num; i <= sum; i++) {
                    dp[i] = (dp[i] + dp[i - num]) % MOD;
                }
                int temp = (c + 1) * num;
                // correction part
                // subtract dp[i - (freq + 1) * num] to the end part.
                // leves dp[i] = dp[i] + dp[i-num] +...+ dp[i - c*num];
                for (int i = sum; i >= temp; i--) {
                    dp[i] = (dp[i] - dp[i - temp] + MOD) % MOD;
                }
            }
            int ans = 0;
            for (int i = l; i <= r; i++) {
                ans += dp[i];
                ans %= MOD;
            }
            return ans;
        }
    }
    

All Problems

All Solutions