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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count of Integers

Difficulty: Hard

Problem Description

You are given two numeric strings num1 and num2 and two integers max_sum and min_sum. We denote an integer x to be good if:

  • num1 <= x <= num2
  • min_sum <= digit_sum(x) <= max_sum

Return the number of good integers. Since the answer may be large, return it modulo 10^9 + 7.

Key Insights

  • The problem involves counting integers within a specified range whose digit sums fall within given bounds.
  • Given the constraints (up to 10^22), a direct approach of iterating through all integers is impractical.
  • A digit dynamic programming (DP) approach can be employed to efficiently count valid integers using properties of digit sums.
  • The digit sum can be computed using properties of numbers in a positional numeral system.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of digits in num2 and m is the range of digit sums (up to 400).
Space Complexity: O(n * m), for storing the DP states.

Solution

To solve this problem, we can use a digit dynamic programming approach:

  1. Convert the numeric strings into lists of digits for easier manipulation.
  2. Use a DP table to keep track of the count of valid integers based on the current digit position, whether we are still constrained by the upper bound (num2), and the current sum of digits.
  3. Use recursive calls to build numbers digit by digit while maintaining the constraints.

Key Data Structures:

  • A DP array to store counts of valid configurations based on current digit position and current digit sum.
  • A memoization structure to avoid recalculating results for the same states.

Code Solutions

def digit_sum_count(num1, num2, min_sum, max_sum):
    MOD = 10**9 + 7
    
    def digit_sum(x):
        return sum(int(d) for d in str(x))
    
    def count_good_integers(low, high, min_s, max_s):
        # Convert to digit lists
        low_digits = [int(d) for d in str(low)]
        high_digits = [int(d) for d in str(high)]
        n = len(high_digits)
        
        # DP table: dp[pos][sum][tight]
        dp = [[[-1 for _ in range(2)] for _ in range(max_s + 1)] for _ in range(n)]
        
        def dfs(pos, sum_d, tight):
            if sum_d > max_s:  # If we exceed max_sum
                return 0
            if pos == n:  # If we are at the end of digits
                return 1 if sum_d >= min_s else 0
            
            if dp[pos][sum_d][tight] != -1:
                return dp[pos][sum_d][tight]
            
            res = 0
            limit = high_digits[pos] if tight else 9
            
            for digit in range(0, limit + 1):
                res += dfs(pos + 1, sum_d + digit, tight and (digit == limit))
                res %= MOD
            
            dp[pos][sum_d][tight] = res
            return res
        
        return dfs(0, 0, 1)

    num1_int = int(num1)
    num2_int = int(num2)
    return (count_good_integers(num1_int, num2_int, min_sum, max_sum) + MOD) % MOD
← Back to All Questions