Count of Integers solution and explanation
Cisco
4 more videos on this problem
Digit DP | 2719. Count of Integers | Leetcode Weekly Contest 348codingMohan · 34:06 · 2K views
L-06. Digit DP | Count of Integers | Leetcode 2719 | Recursive + Memoization | Intuition + CodeWhy Not DP [By Piyush Raj] · 34:52 · 1K views
2719. Count of Integers (Leetcode Hard)Programming Live with Larry · 30:14 · 780 views
【每日一题】LeetCode 2719. Count of IntegersHuifeng Guan · 21:35 · 593 views
Count of Integers - LeetCode 2719 - PythonAlpha-Code · 23:59 · 442 views
The 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 <= num2min_sum <= digit_sum(x) <= max_sum.
Return the number of good integers. Since the answer may be large, return it modulo 109 + 7.
Note that digit_sum(x) denotes the sum of the digits of x.
Example 1:
Input: num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
Output: 11
Explanation: There are 11 integers whose sum of digits lies between 1 and 8 are 1,2,3,4,5,6,7,8,10,11, and 12. Thus, we return 11.
Example 2:
Input: num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
Output: 5
Explanation: The 5 integers whose sum of digits lies between 1 and 5 are 1,2,3,4, and 5. Thus, we return 5.
Constraints:
1 <= num1 <= num2 <= 10221 <= min_sum <= max_sum <= 400
Approach overview
Problem Overview: You are given two numeric strings num1 and num2. Count how many integers in the inclusive range satisfy a constraint where the sum of their digits falls between min_sum and max_sum.
Approach 1: Iterative Brute Force (O(R * d) time, O(1) space)
The direct method iterates through every integer from num1 to num2. For each number, compute the digit sum and check whether it lies between min_sum and max_sum. If the range size is R and each number has up to d digits, the cost is O(R * d). This works only for small ranges because the numbers can be very large (up to 1022). The approach mainly demonstrates the baseline logic: convert each number to a string or repeatedly extract digits to compute the sum.
Approach 2: Digit Dynamic Programming (Digit DP) (O(d * maxSum * 10) time, O(d * maxSum) space)
The efficient solution counts valid numbers without enumerating them. Instead of iterating through the range, compute how many valid integers exist from 0 to a bound using digit DP, then subtract results: count(num2) - count(num1 - 1). The DP state typically tracks (position, currentSum, tight). position indicates the current digit index, currentSum tracks the accumulated digit sum, and tight indicates whether the prefix is restricted by the upper bound.
At each digit, try placing digits from 0 to the allowed limit. Update the running digit sum and propagate the tight constraint if the chosen digit matches the bound digit. Memoization avoids recomputing states. Because the number of digits is small and the sum range is bounded, the total states remain manageable.
This technique is common in problems involving numeric ranges and digit properties. It combines ideas from dynamic programming, math, and string processing to efficiently explore all valid numbers.
Recommended for interviews: Digit DP is the expected solution. Brute force shows you understand the problem constraints, but it fails for large ranges. Implementing a memoized digit DP demonstrates strong control over state design, boundary handling, and optimization.
Approach 1: Iterative Brute Force
This method involves iterating over each integer between num1 and num2, calculating their digit sums, and counting those within the given range. Though simple, this approach considers each number individually and checks if it satisfies the conditions.
MOD = 1000000007
def digit_sum(num):
return sum(int(digit) for digit in num)
def is_good(num, min_sum, max_sum):
return min_sum <= digit_sum(num) <= max_sum
def count_good_integers(num1, num2, min_sum, max_sum):
count = 0
start = int(num1)
end = int(num2)
for i in range(start, end + 1):
num_str = str(i)
if is_good(num_str, min_sum, max_sum):
count = (count + 1) % MOD
return count
# Examples
print(count_good_integers("1", "12", 1, 8))
print(count_good_integers("1", "5", 1, 5))class Solution {
final static int MOD = 1000000007;
public int digitSum(String num) {
int sum = 0;
for (int i = 0; i < num.length(); i++) {
sum += num.charAt(i) - '0';
}
return sum;
}
public boolean isGood(String num, int minSum, int maxSum) {
int sum = digitSum(num);
return sum >= minSum && sum <= maxSum;
}
public int countGoodIntegers(String num1, String num2, int minSum, int maxSum) {
long count = 0;
long start = Long.parseLong(num1);
long end = Long.parseLong(num2);
for (long i = start; i <= end; i++) {
String numStr = String.valueOf(i);
if (isGood(numStr, minSum, maxSum)) {
count = (count + 1) % MOD;
}
}
return (int) count;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.countGoodIntegers("1", "12", 1, 8));
System.out.println(sol.countGoodIntegers("1", "5", 1, 5));
}
}#include <iostream>
#include <string>
using namespace std;
const int MOD = 1000000007;
int digitSum(const string &num) {
int sum = 0;
for (char c : num) {
sum += c - '0';
}
return sum;
}
bool isGood(const string &num, int min_sum, int max_sum) {
int sum = digitSum(num);
return sum >= min_sum && sum <= max_sum;
}
int countGoodIntegers(const string &num1, const string &num2, int min_sum, int max_sum) {
long long count = 0;
long long start = stoll(num1);
long long end = stoll(num2);
for (long long i = start; i <= end; ++i) {
string num_str = to_string(i);
if (isGood(num_str, min_sum, max_sum)) {
count = (count + 1) % MOD;
}
}
return count;
}
int main() {
cout << countGoodIntegers("1", "12", 1, 8) << endl;
cout << countGoodIntegers("1", "5", 1, 5) << endl;
return 0;
}const MOD = 1000000007;
function digitSum(num) {
return num.split('').reduce((sum, digit) => sum + parseInt(digit), 0);
}
function isGood(num, minSum, maxSum) {
const sum = digitSum(num);
return sum >= minSum && sum <= maxSum;
}
function countGoodIntegers(num1, num2, minSum, maxSum) {
let count = 0;
const start = BigInt(num1);
const end = BigInt(num2);
for (let i = start; i <= end; i++) {
const numStr = i.toString();
if (isGood(numStr, minSum, maxSum)) {
count = (count + 1) % MOD;
}
}
return count;
}
console.log(countGoodIntegers("1", "12", 1, 8));
console.log(countGoodIntegers("1", "5", 1, 5));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MOD 1000000007
int digit_sum(const char* num) {
int sum = 0;
for (int i = 0; num[i] != '\0'; i++) {
sum += num[i] - '0';
}
return sum;
}
int is_good(const char* num, int min_sum, int max_sum) {
int sum = digit_sum(num);
return sum >= min_sum && sum <= max_sum;
}
int count_good_integers(const char* num1, const char* num2, int min_sum, int max_sum) {
long long count = 0;
long long start = atoll(num1);
long long end = atoll(num2);
for (long long i = start; i <= end; i++) {
char num_str[23];
sprintf(num_str, "%lld", i);
if (is_good(num_str, min_sum, max_sum)) {
count++;
count %= MOD;
}
}
return (int) count;
}
int main() {
printf("%d\n", count_good_integers("1", "12", 1, 8));
printf("%d\n", count_good_integers("1", "5", 1, 5));
return 0;
}using System;
class Solution {
const int MOD = 1000000007;
public int DigitSum(string num) {
int sum = 0;
foreach (char c in num) {
sum += c - '0';
}
return sum;
}
public bool IsGood(string num, int minSum, int maxSum) {
int sum = DigitSum(num);
return sum >= minSum && sum <= maxSum;
}
public int CountGoodIntegers(string num1, string num2, int minSum, int maxSum) {
long count = 0;
long start = long.Parse(num1);
long end = long.Parse(num2);
for (long i = start; i <= end; i++) {
string numStr = i.ToString();
if (IsGood(numStr, minSum, maxSum)) {
count = (count + 1) % MOD;
}
}
return (int) count;
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.CountGoodIntegers("1", "12", 1, 8));
Console.WriteLine(sol.CountGoodIntegers("1", "5", 1, 5));
}
}This Python solution employs simple integers and loops over each possible integer between num1 and num2, ensuring the digit sum fits the defined criteria.
The time complexity is O(N*M) due to number conversion and digit sum checks, and the space complexity is O(1).
Approach 2: Dynamic Programming with Digit DP
This approach uses dynamic programming concepts, specifically digit-based dynamic programming, to efficiently compute the number of good integers by understanding properties of digit sums and bounds. By breaking the number problem into subproblems per digit, we reduce unnecessary recalculation.
import java.util.*;
class Solution {
static final int MOD = 1000000007;
int[][][] dp;
private int digitDP(int pos, int sum, boolean tight, String num, int minSum, int maxSum) {
if (pos == num.length()) return sum >= minSum && sum <= maxSum ? 1 : 0;
if (dp[pos][sum][tight ? 1 : 0] != -1) return dp[pos][sum][tight ? 1 : 0];
int limit = tight ? num.charAt(pos) - '0' : 9;
int res = 0;
for (int dig = 0; dig <= limit; dig++) {
res = (res + digitDP(pos + 1, sum + dig, tight && (dig == limit), num, minSum, maxSum)) % MOD;
}
return dp[pos][sum][tight ? 1 : 0] = res;
}
public int countGoodIntegers(String num1, String num2, int minSum, int maxSum) {
dp = new int[num2.length()][401][2];
for (int[][] d1 : dp) for (int[] d2 : d1) Arrays.fill(d2, -1);
int res2 = digitDP(0, 0, true, num2, minSum, maxSum);
dp = new int[num1.length()][401][2];
for (int[][] d1 : dp) for (int[] d2 : d1) Arrays.fill(d2, -1);
int res1 = digitDP(0, 0, true, num1, minSum, maxSum);
return (res2 - res1 + MOD) % MOD;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.countGoodIntegers("1", "12", 1, 8));
System.out.println(s.countGoodIntegers("1", "5", 1, 5));
}
}#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int digitDP(int pos, int sum, bool tight, const string &num, int min_sum, int max_sum, vector<vector<vector<int>>> &dp) {
if (pos == num.size()) return sum >= min_sum && sum <= max_sum ? 1 : 0;
if (dp[pos][sum][tight] != -1) return dp[pos][sum][tight];
int limit = tight ? num[pos] - '0' : 9;
int res = 0;
for (int dig = 0; dig <= limit; ++dig) {
res = (res + digitDP(pos + 1, sum + dig, tight && (dig == limit), num, min_sum, max_sum, dp)) % MOD;
}
return dp[pos][sum][tight] = res;
}
int countGoodIntegers(const string &num1, const string &num2, int min_sum, int max_sum) {
vector<vector<vector<int>>> dp(num2.size(), vector<vector<int>>(401, vector<int>(2, -1)));
int res2 = digitDP(0, 0, true, num2, min_sum, max_sum, dp);
dp = vector<vector<vector<int>>>(num1.size(), vector<vector<int>>(401, vector<int>(2, -1)));
int res1 = digitDP(0, 0, true, num1, min_sum, max_sum, dp);
return (res2 - res1 + MOD) % MOD;
}
int main() {
cout << countGoodIntegers("1", "12", 1, 8) << endl;
cout << countGoodIntegers("1", "5", 1, 5) << endl;
return 0;
}This Java solution applies the digit DP approach. The function countGoodIntegers initializes the DP array and computes results for both boundaries. digitDP recursively computes viable numbers with digit sums within specified limits.
Time complexity is similar to C++, O(D*sum_bound*TightStates), with space complexity O(D*sum_bound*TightStates).
Approach 3: Digit DP
The problem is actually asking for the number of integers in the range [num1,..num2] whose digit sum is in the range [min_sum,..max_sum]. For this kind of range [l,..r] problem, we can consider transforming it into finding the answers for [1,..r] and [1,..l-1], and then subtracting the latter from the former.
For the answer to [1,..r], we can use digit DP to solve it. We design a function dfs(pos, s, limit), which represents the number of schemes when we are currently processing the posth digit, the digit sum is s, and whether the current number has an upper limit limit. Here, pos is enumerated from high to low.
For dfs(pos, s, limit), we can enumerate the value of the current digit i, and then recursively calculate dfs(pos+1, s+i, limit \bigcap i==up), where up represents the upper limit of the current digit. If limit is true, then up is the upper limit of the current digit, otherwise up is 9. If pos is greater than or equal to the length of num, then we can judge whether s is in the range [min_sum,..max_sum]. If it is, return 1, otherwise return 0.
The time complexity is O(10 times n times max_sum), and the space complexity is O(n times max_sum). Here, n represents the length of num.
Similar problems:
function count(num1: string, num2: string, min_sum: number, max_sum: number): number {
const mod = 1e9 + 7;
const f: number[][] = Array.from({ length: 23 }, () => Array(220).fill(-1));
let num = num2;
const dfs = (pos: number, s: number, limit: boolean): number => {
if (pos >= num.length) {
return s >= min_sum && s <= max_sum ? 1 : 0;
}
if (!limit && f[pos][s] !== -1) {
return f[pos][s];
}
let ans = 0;
const up = limit ? +num[pos] : 9;
for (let i = 0; i <= up; i++) {
ans = (ans + dfs(pos + 1, s + i, limit && i === up)) % mod;
}
if (!limit) {
f[pos][s] = ans;
}
return ans;
};
const a = dfs(0, 0, true);
num = (BigInt(num1) - 1n).toString();
f.forEach(v => v.fill(-1));
const b = dfs(0, 0, true);
return (a - b + mod) % mod;
}func count(num1 string, num2 string, min_sum int, max_sum int) int {
const mod = 1e9 + 7
f := [23][220]int{}
for i := range f {
for j := range f[i] {
f[i][j] = -1
}
}
num := num2
var dfs func(int, int, bool) int
dfs = func(pos, s int, limit bool) int {
if pos >= len(num) {
if s >= min_sum && s <= max_sum {
return 1
}
return 0
}
if !limit && f[pos][s] != -1 {
return f[pos][s]
}
var ans int
up := 9
if limit {
up = int(num[pos] - '0')
}
for i := 0; i <= up; i++ {
ans = (ans + dfs(pos+1, s+i, limit && i == up)) % mod
}
if !limit {
f[pos][s] = ans
}
return ans
}
a := dfs(0, 0, true)
t := []byte(num1)
for i := len(t) - 1; i >= 0; i-- {
if t[i] != '0' {
t[i]--
break
}
t[i] = '9'
}
num = string(t)
f = [23][220]int{}
for i := range f {
for j := range f[i] {
f[i][j] = -1
}
}
b := dfs(0, 0, true)
return (a - b + mod) % mod
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Brute Force | The time complexity is O(N*M) due to number conversion and digit sum checks, and the space complexity is O(1). |
| Dynamic Programming with Digit DP | Time complexity is similar to C++, O(D*sum_bound*TightStates), with space complexity O(D*sum_bound*TightStates). |
| Digit DP | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Brute Force | O(R * d) | O(1) | Only when the numeric range is very small and numbers fit standard integer limits |
| Digit Dynamic Programming (Digit DP) | O(d * maxSum * 10) | O(d * maxSum) | Large ranges with digit constraints; standard technique for counting numbers with digit properties |
Frequently asked questions
Is Count of Integers easy or hard?
Count of Integers is considered a hard problem because it requires understanding and implementing Digit Dynamic Programming. Handling range boundaries, digit sums, and memoization states correctly adds significant complexity compared to standard DP problems.
Count of Integers Python/Java solution
Both Python and Java implementations typically use recursion with memoization for the Digit DP state (position, sum, tight). The algorithm calculates the count of valid numbers up to a limit and subtracts results for the lower bound. This ensures the full range [num1, num2] is handled correctly.
How to solve Count of Integers in O(n)?
The problem cannot be solved in strict linear time over the numeric range because the numbers can be extremely large. Instead, Digit DP counts valid numbers by processing digits of the bounds. The complexity becomes O(d * maxSum * 10), which is effectively linear in the number of digits rather than the size of the range.
What is the best approach for Count of Integers?
The optimal solution uses Digit Dynamic Programming (Digit DP). Instead of iterating through every number in the range, compute how many valid numbers exist up to a bound using a DP state like (position, digitSum, tight). The final result is count(num2) minus count(num1 - 1). This runs in O(d * maxSum * 10) time.
Is Count of Integers asked at Google/Amazon/Meta?
Digit DP problems similar to Count of Integers frequently appear in interviews at companies like Google, Amazon, and Meta. These companies often test candidates on counting problems with digit constraints, range limits, and memoized recursion.
What data structure is used in Count of Integers?
The core structure is a memoization table used in dynamic programming. The DP state usually includes the current digit index, accumulated digit sum, and a tight constraint flag. Recursion or iterative DP is used to explore all digit placements efficiently.
What is the time complexity of Count of Integers?
The optimal Digit DP solution runs in O(d * maxSum * 10) time where d is the number of digits in the bound. The DP explores each digit position, possible digit choices (0–9), and valid digit sums. Space complexity is O(d * maxSum) due to memoization.