Count Good Integers in a Range - Solution & Explanation

Problem Overview: You are given a numeric range [low, high]. The task is to count how many integers in this range satisfy a specific digit-based constraint that defines a “good” integer. Since the range can be large, checking each value directly becomes inefficient and requires a smarter counting strategy.

Approach 1: Brute Force Enumeration (O(n * d) time, O(1) space)

The most direct method iterates through every integer from low to high. For each number, convert it to digits and check whether it satisfies the required condition that defines a good integer. The validation typically scans the digits and evaluates the rule (for example checking digit relationships, constraints, or computed properties). This approach is easy to implement and useful for validating correctness on small inputs, but the time complexity becomes prohibitive when the range spans millions or billions of values.

Approach 2: Digit Dynamic Programming (Digit DP) (O(d * states * 10) time, O(d * states) space)

When the property of a “good integer” depends on its digits, the standard optimization is digit DP. Instead of iterating over every number, you build numbers digit-by-digit and count valid combinations. The DP state typically tracks the current digit index, whether the prefix is still tight with the upper bound, and additional state required to verify the property (for example a remainder, mask, or previous digit). At each step you iterate over digits 0–9 and update the state accordingly. Memoization avoids recomputing states that appear repeatedly.

To count numbers in a range, compute count(high) and subtract count(low - 1). Each call runs the digit DP over the string representation of the bound. This technique reduces the search space from potentially billions of integers to roughly d * states * 10, where d is the number of digits.

Approach 3: Digit DP with State Compression (O(d * states * 10) time, O(states) space)

In some versions of the problem, the digit constraint involves sets or combinations of digits. You can compress this information into bitmasks or compact integer states. For example, a 10-bit mask can represent used digits, or a small integer can track a modulo remainder. This keeps transitions constant-time and makes memoization efficient. The DP cache is reused across recursive calls except when the prefix is tight with the bound.

Recommended for interviews: Interviewers expect the digit DP solution. Start by explaining the brute-force scan to show the baseline complexity. Then transition to building numbers digit-by-digit with a tight constraint and memoization. That demonstrates strong understanding of range counting problems. Similar patterns appear in problems involving digit constraints, counting valid numbers, and combinatorial digit states within dynamic programming, backtracking, and math-driven counting techniques.