Is Count Good Integers in a Range easy or hard?

The problem is classified as Hard because it requires recognizing when to apply digit DP and designing the correct state representation. Once the state and transitions are defined, the implementation becomes a structured recursive DP with memoization.

Count Good Integers in a Range Python/Java solution

Most implementations use a recursive digit DP helper that processes digits of the bound as a string. Python solutions commonly rely on functools.lru_cache for memoization, while Java implementations use arrays or HashMap-based DP tables to store computed states.

How to solve Count Good Integers in a Range in O(n)?

A direct O(n) scan iterates through every integer in the interval and checks whether it satisfies the condition. While simple, this approach only works for small ranges. For large bounds, digit DP is preferred because it avoids enumerating every value explicitly.

What is the best approach for Count Good Integers in a Range?

The most efficient solution uses Digit Dynamic Programming (Digit DP). Instead of checking every number in the range, the algorithm constructs numbers digit by digit while respecting the upper bound and tracking state needed to validate the rule defining a good integer. This reduces the search to roughly O(d * states * 10), where d is the number of digits.

Is Count Good Integers in a Range asked at Google/Amazon/Meta?

Range-counting problems using digit DP appear frequently in interviews at companies like Google, Amazon, and Meta. Variations often involve counting numbers with digit constraints, forbidden patterns, or remainder conditions within a large numeric range.

What data structure is used in Count Good Integers in a Range?

The core technique relies on recursion with memoization or a DP table. States are typically stored in a hash map or multidimensional array indexed by digit position, tight constraint, and additional state such as masks or remainders.

What is the time complexity of Count Good Integers in a Range?

The optimal digit DP approach runs in O(d * states * 10) time and O(d * states) space. The value d represents the number of digits in the upper bound, while states represent the additional information required to enforce the constraint (such as masks, remainders, or previous digits).

Description Hints 3 Video 27:18

3966. Count Good Integers in a Range

Hard49.8% acceptance

You are given three integers l, r and k.

A number is considered good if the absolute difference between every pair of adjacent digits is at most k.

Return the number of good integers in the range [l, r] (inclusive).

The absolute difference between values x and y is defined as abs(x - y).

Example 1:

Input: l = 10, r = 15, k = 1

Output: 3

Explanation:

The good integers in the range are 10, 11, and 12.
For 10, abs(1 - 0) = 1.
For 11, abs(1 - 1) = 0.
For 12, abs(1 - 2) = 1.
All these differences are at most k = 1. Thus, the answer is 3.

Example 2:

Input: l = 201, r = 204, k = 2

Output: 2

Explanation:

The good integers in the range are 201 and 202.
For 201, abs(2 - 0) = 2 and abs(0 - 1) = 1.
For 202, abs(2 - 0) = 2 and abs(0 - 2) = 2.
Thus, the answer is 2.

Constraints:

10 <= l <= r <= 10¹⁵
0 <= k <= 9

Topics

Dynamic Programming Math

Hints open one at a time

Hint 1

Count good integers less than or equal to some bound x, then subtract the count for l - 1 from the count for r.

Hint 2

Use digit DP over the decimal representation of x.

Hint 3

Keep the previous digit in the DP state, and when placing the next digit, ensure the absolute difference is at most k.

LanguageLoading editor…

1class Solution:
2    def goodIntegers(self, l: int, r: int, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

10
15
1

Input

201
204
2

Your code is saved on this device.