Count of Integers - Practice Coding Problems

Count of Integers - Problem

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.

Note: digit_sum(x) denotes the sum of the digits of x.

Input & Output

Example 1 — Basic Range

$ Input: num1 = "1", num2 = "12", min_sum = 1, max_sum = 8

› Output: 11

💡 Note: Numbers 1-12 have digit sums: 1(1), 2(2), 3(3), 4(4), 5(5), 6(6), 7(7), 8(8), 9(9), 10(1), 11(2), 12(3). All have digit sum ≤ 8, so count = 11.

Example 2 — Narrow Sum Range

$ Input: num1 = "1", num2 = "5", min_sum = 1, max_sum = 3

› Output: 3

💡 Note: Numbers 1,2,3 have digit sums 1,2,3 respectively (all valid). Numbers 4,5 have digit sums 4,5 (both > 3, invalid). Count = 3.

Example 3 — Single Number

$ Input: num1 = "15", num2 = "15", min_sum = 5, max_sum = 8

› Output: 1

💡 Note: Only number 15 in range. Digit sum = 1+5 = 6, which satisfies 5 ≤ 6 ≤ 8. Count = 1.

Constraints

1 ≤ num1 ≤ num2 < 10²²
1 ≤ min_sum ≤ max_sum ≤ 400

Visualization

Tap to expand

Understanding the Visualization

Input

Range [num1, num2] and digit sum bounds [min_sum, max_sum]

Process

Use digit DP to count valid numbers efficiently

Output

Count of numbers satisfying both range and digit sum constraints

Key Takeaway

🎯 Key Insight: Use digit DP to build valid numbers systematically rather than checking every number in the range

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to use digit DP to efficiently count valid numbers by building them position by position while tracking constraints. The optimal approach uses memoized recursion with states (position, digit_sum, tight_bound, started). Time: O(d × S × 2 × 2 × 10), Space: O(d × S × 2 × 2).

Common Approaches

Approach	Time	Space	Notes
✓ Digit DP with Memoization	O(d * S * 2 * 2 * 10)	O(d * S * 2 * 2)	Use digit dynamic programming to build valid numbers position by position
Brute Force Iteration	O(N * d)	O(1)	Iterate through all numbers in range and check digit sum constraints

Digit DP with Memoization — Algorithm Steps

Define DP state: position, sum_so_far, tight_bound, started
Build number digit by digit with constraints
Use memoization to cache computed states
Sum all valid paths that reach the end

Visualization

Tap to expand

Step-by-Step Walkthrough

State

Track position, digit sum, tight constraint, started flag

Choices

At each position, try valid digits (0-9 or up to tight bound)

Memoize

Cache results to avoid recomputing same states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAXN 25
#define MAXSUM 200

int memo[MAXN][MAXSUM][2][2];
int visited[MAXN][MAXSUM][2][2];
char num_str[MAXN];
int minSum, maxSum, len;

int dp(int pos, int sumSoFar, int tight, int started) {
    if (pos == len) {
        return (started && minSum <= sumSoFar && sumSoFar <= maxSum) ? 1 : 0;
    }
    
    if (visited[pos][sumSoFar][tight][started]) {
        return memo[pos][sumSoFar][tight][started];
    }
    
    int limit = tight ? (num_str[pos] - '0') : 9;
    int result = 0;
    
    for (int digit = 0; digit <= limit; digit++) {
        int newTight = tight && (digit == limit);
        int newStarted = started || (digit > 0);
        int newSum = sumSoFar + digit;
        
        if (newSum <= maxSum) {
            result = (result + dp(pos + 1, newSum, newTight, newStarted)) % MOD;
        }
    }
    
    visited[pos][sumSoFar][tight][started] = 1;
    return memo[pos][sumSoFar][tight][started] = result;
}

int countValid(char* s) {
    strcpy(num_str, s);
    len = strlen(s);
    memset(visited, 0, sizeof(visited));
    return dp(0, 0, 1, 0);
}

void subtractOne(char* s, char* result) {
    strcpy(result, s);
    int i = strlen(result) - 1;
    
    while (i >= 0 && result[i] == '0') {
        result[i] = '9';
        i--;
    }
    
    if (i >= 0) {
        result[i]--;
    }
    
    // Remove leading zeros
    int start = 0;
    while (result[start] == '0' && result[start + 1] != '\0') {
        start++;
    }
    
    if (start > 0) {
        memmove(result, result + start, strlen(result) - start + 1);
    }
}

int solution(char* num1, char* num2, int min_sum, int max_sum) {
    minSum = min_sum;
    maxSum = max_sum;
    
    char num1_minus_one[MAXN];
    subtractOne(num1, num1_minus_one);
    
    int count2 = countValid(num2);
    int count1 = countValid(num1_minus_one);
    
    return (count2 - count1 + MOD) % MOD;
}

int main() {
    char num1[MAXN], num2[MAXN];
    int min_sum, max_sum;
    
    fgets(num1, sizeof(num1), stdin);
    num1[strcspn(num1, "\n")] = 0;
    
    fgets(num2, sizeof(num2), stdin);
    num2[strcspn(num2, "\n")] = 0;
    
    scanf("%d", &min_sum);
    scanf("%d", &max_sum);
    
    int result = solution(num1, num2, min_sum, max_sum);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(d * S * 2 * 2 * 10)

d digits, S max sum, 2 tight flags, 2 started flags, 10 possible digit choices

✓ Linear Growth

Space Complexity

O(d * S * 2 * 2)

Memoization table stores states for position, sum, tight, started flags

✓ Linear Space

12.8K Views

Medium Frequency

~35 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Digit DP with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler