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.

Description Hints 3 Solution Video 34:06

2719. Count of Integers

Hard38.9% acceptance2 companies

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⁹ + 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 <= 10²²
1 <= min_sum <= max_sum <= 400

Asked at 2 companies

Cisco Goldman Sachs

Topics

Hints open one at a time

Hint 1

Let f(n, l, r) denotes the number of integers from 1 to n with the sum of digits between l and r.

Hint 2

The answer is f(num2, min_sum, max_sum) - f(num-1, min_sum, max_sum).

Hint 3

You can calculate f(n, l, r) using digit dp.

34:06

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution