3747. Count Distinct Integers After Removing Zeros

MediumMathDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a positive integer n.

For every integer x from 1 to n, we write down the integer obtained by removing all zeros from the decimal representation of x.

Return an integer denoting the number of distinct integers written down.

In other words, for each x in the range [1, n], we delete every digit 0 from x and keep the remaining digits in their original order to form a new number. After doing this for all values of x, we count how many different results we end up with.

For example, if x = 102, removing all zeros gives 12. If x = 12, removing all zeros also gives 12. So these two values of x produce the same written-down integer, and they should only be counted once.

The key observation is that every integer obtained by removing zeros is itself an integer that contains no zero digits. Moreover, each zero-free integer in the range [1, n] is written down exactly once (by x equal to itself), and any number with zeros maps onto some smaller zero-free number. Therefore, the count of distinct integers written down is exactly the count of integers in [1, n] that do not contain the digit 0.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Dynamic programming over states or positions computes the answer efficiently.

Open in Flowchart

Intuition

Let's think about what happens when we remove all zeros from each number x.

The first thing to notice is that whatever result we get after removing zeros, it is always a number that contains no zero digits. So every "written down" integer belongs to the set of zero-free numbers.

Now we ask: which zero-free numbers actually appear, and how many times does each one appear? Consider any zero-free number y that lies in the range [1, n]. When x equals y itself, removing zeros from y changes nothing (since y has no zeros), so y writes itself down. This means every zero-free number in [1, n] is guaranteed to appear at least once.

On the other hand, any number x that contains zeros will, after removal, collapse onto some zero-free number that is smaller than x. So numbers with zeros never create a new distinct value—they only duplicate a zero-free number that is already counted.

Putting these two facts together: the set of distinct integers we write down is exactly the set of zero-free integers in [1, n]. Counting the answer therefore reduces to counting how many integers from 1 to n have no digit equal to 0.

This is now a classic counting numbers under a constraint up to a bound problem. Since n can be large, we don't want to loop through every value. Instead, we count digit by digit, deciding each digit from the highest position to the lowest while making sure we never exceed n. This naturally leads to a digit DP approach, where we track:

lim: whether the digits chosen so far are still tight against n's prefix (so the next digit can't go beyond n's digit).
lead: whether we are still in the leading-zero region (leading zeros are allowed because they don't really count as a digit 0 in the number).
zero: whether an actual digit 0 has appeared after the number has started, which would make the number invalid for our count.

By exploring all valid digit choices recursively and using memoization to avoid recomputing identical states, we efficiently count exactly the zero-free numbers in [1, n].

Pattern Learn more about Math and Dynamic Programming patterns.

Solution Approach

Solution 1: Digit DP

As established, the problem reduces to counting the integers in the range [1, n] that do not contain the digit 0. We solve this using digit DP.

We design a function dfs(i, zero, lead, lim), which represents the number of valid solutions when we are currently processing the i-th digit of the number (from left to right). The meaning of each parameter is:

i: the index of the digit we are currently deciding within s, where s = str(n).
zero: whether a digit 0 has appeared in the current number after it has actually started (i.e., a real zero, not a leading zero).
lead: whether we are still in the leading-zero region, meaning no non-zero digit has been placed yet.
lim: whether the digits chosen so far are tight against the prefix of n, which constrains how large the current digit may be.

The answer is dfs(0, False, True, True): we start at the first digit, no real zero has appeared yet, we are still handling leading zeros, and we are limited by the bound n.

Base case. When i >= len(s), we have finished building a number. We check zero and lead:

If not zero and not lead, it means the number has actually started (so it is at least 1) and it contains no real 0, so this is a valid number and we return 1.
Otherwise we return 0. The lead being true here means the number is still all leading zeros (i.e., it represents 0, which is outside [1, n]), and zero being true means a forbidden digit 0 appeared.

Transition. For dfs(i, zero, lead, lim):

We compute the upper bound up for the current digit. If lim is true, then up = int(s[i]) because we cannot exceed n's digit at this position; otherwise up = 9, since any digit is allowed.
We enumerate the current digit j from 0 to up, and accumulate the results of the recursive calls. For each choice of j, we update the three flags:
- nxt_zero = zero or (j == 0 and not lead): a real zero appears when we place 0 and we are no longer in the leading-zero region.
- nxt_lead = lead and j == 0: we remain in the leading-zero region only if we were already in it and we place another 0.
- nxt_lim = lim and j == up: we stay tight against the bound only if we were tight and we chose exactly the maximum allowed digit.
We sum up dfs(i + 1, nxt_zero, nxt_lead, nxt_lim) over all valid j and return the total.

Memoization. The function is decorated with @cache, so repeated states are computed only once. This is what makes the approach efficient: instead of iterating over all n values, we count along the digit positions.

Data structure / pattern. The core pattern is digit DP with recursion plus memoization. The string s = str(n) provides constant-time access to each digit, and the boolean flags zero, lead, and lim together encode the state needed to count correctly without exceeding n.

The time complexity is O(log n) in terms of the number of digits multiplied by the constant number of states and digit choices, since each digit position has at most 10 choices and a small fixed number of flag combinations. The space complexity is also proportional to the number of cached states, which is O(log n).

Example Walkthrough

Let's trace through the solution approach with the small example n = 12.

First, recall the key reduction: the number of distinct integers written down equals the count of integers in [1, 12] that contain no digit 0. Let's verify this by hand, then watch the digit DP compute the same answer.

Manual check. The integers from 1 to 12 are:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

Removing zeros from each:

1..9 → 1..9 (unchanged, all zero-free)
10 → 1 (collapses onto the already-counted 1)
11 → 11
12 → 12

The distinct results are {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12}, which is 11 values. Notice this is exactly the set of zero-free numbers in [1, 12] — 10 is the only number with a zero, and it adds nothing new. So the expected answer is 11.

Digit DP trace. We set s = "12", so len(s) = 2, and call dfs(0, zero=False, lead=True, lim=True).

Position i = 0 (the tens digit). Since lim=True, the upper bound is up = int(s[0]) = 1. We enumerate j from 0 to 1:

j = 0 (place a leading zero):
- nxt_zero = False or (True and not True) = False (still a leading zero, not a real zero)
- nxt_lead = True and j==0 = True (still in leading-zero region)
- nxt_lim = True and (0 == 1) = False (we dropped below n's digit, no longer tight)
- Recurse into dfs(1, zero=False, lead=True, lim=False). Here up = 9. We count single-digit numbers freely:
  - j = 0 → stays lead=True, zero=False → at base case, lead is true → contributes 0 (this is the number 0, excluded).
  - j = 1..9 → lead becomes False, zero stays False → each reaches the base case valid → contributes 9.
- Subtotal from this branch: 9 (these represent the numbers 1 through 9).
j = 1 (place the tens digit 1, staying tight):
- nxt_zero = False
- nxt_lead = True and (1==0) = False (number has started)
- nxt_lim = True and (1 == 1) = True (still tight against n)
- Recurse into dfs(1, zero=False, lead=False, lim=True). Now up = int(s[1]) = 2. We enumerate the units digit j from 0 to 2:
  - j = 0 → nxt_zero = False or (True) = True (a real zero appears — this is the number 10) → at base case zero is true → contributes 0.
  - j = 1 → no zero, valid → represents 11 → contributes 1.
  - j = 2 → no zero, still tight, valid → represents 12 → contributes 1.
- Subtotal from this branch: 2 (the numbers 11 and 12; 10 correctly excluded).

Total. dfs(0, ...) returns 9 + 2 = 11.

This matches our manual count exactly. The DP elegantly skipped 10 because placing 0 after the number started flipped nxt_zero to True, marking that path invalid — confirming that only zero-free numbers in [1, n] are counted.

Solution Implementation

1from functools import cache
2
3
4class Solution:
5    def countDistinct(self, n: int) -> int:
6        # Convert n to its string form so we can process digit by digit.
7        s = str(n)
8
9        @cache
10        def dfs(index: int, has_zero: bool, is_leading: bool, is_limit: bool) -> int:
11            """
12            Count valid numbers formed from position `index` onward.
13
14            index:       current digit position being filled
15            has_zero:    True if a zero digit has appeared in the actual number
16                         (i.e., a zero that is not part of the leading-zero prefix)
17            is_leading:  True while we are still inside the leading-zero prefix
18                         (no significant digit chosen yet)
19            is_limit:    True if the chosen prefix exactly matches n's prefix,
20                         which bounds the current digit's upper limit
21            """
22            # Reached the end: a number is valid only if it has no zero digit
23            # and is not an empty (all-leading-zero) construction.
24            if index >= len(s):
25                return 1 if (not has_zero and not is_leading) else 0
26
27            # Upper bound for the current digit: limited by n when tight, else 9.
28            upper = int(s[index]) if is_limit else 9
29
30            count = 0
31            for digit in range(upper + 1):
32                # A zero counts as a "zero digit" only once we are past leading zeros.
33                next_has_zero = has_zero or (digit == 0 and not is_leading)
34                # We remain in the leading-zero prefix only if we keep choosing 0.
35                next_is_leading = is_leading and digit == 0
36                # Stay tight only if we are tight now and pick the boundary digit.
37                next_is_limit = is_limit and digit == upper
38
39                count += dfs(
40                    index + 1,
41                    next_has_zero,
42                    next_is_leading,
43                    next_is_limit,
44                )
45            return count
46
47        return dfs(0, False, True, True)
48

1class Solution {
2    // The decimal digits of n, stored as a char array
3    private char[] digits;
4    // Memoization table: f[index][hasZero][isLeading][isLimited]
5    private Long[][][][] memo;
6
7    public long countDistinct(long n) {
8        digits = String.valueOf(n).toCharArray();
9        // Dimensions: position, hasZero (0/1), isLeading (0/1), isLimited (0/1)
10        memo = new Long[digits.length][2][2][2];
11        // Start: position 0, no zero yet, still in leading-zero region, bounded by n
12        return dfs(0, 0, 1, 1);
13    }
14
15    /**
16     * Digit DP recursion.
17     *
18     * @param index     current digit position being filled
19     * @param hasZero   1 if a real (non-leading) zero digit has already appeared
20     * @param isLeading 1 if we are still in the leading-zero prefix (no significant digit placed yet)
21     * @param isLimited 1 if the digits chosen so far exactly match n's prefix (upper bound still applies)
22     * @return the count of valid numbers from this state onward
23     */
24    private long dfs(int index, int hasZero, int isLeading, int isLimited) {
25        // Base case: all positions processed
26        if (index == digits.length) {
27            // Valid only if no zero digit appeared and the number is non-empty
28            return (hasZero == 0 && isLeading == 0) ? 1 : 0;
29        }
30
31        // Use cached result only for the unconstrained branch (isLimited == 0)
32        if (isLimited == 0 && memo[index][hasZero][isLeading][isLimited] != null) {
33            return memo[index][hasZero][isLeading][isLimited];
34        }
35
36        // Upper bound for the current digit: bounded by n's digit if still limited, else 9
37        int upperBound = isLimited == 1 ? digits[index] - '0' : 9;
38        long count = 0;
39
40        for (int d = 0; d <= upperBound; d++) {
41            // A real zero occurs if one already existed,
42            // or if we place 0 after leaving the leading region
43            int nextHasZero = (hasZero == 1 || (d == 0 && isLeading == 0)) ? 1 : 0;
44            // Still leading only if we were leading and placed another 0
45            int nextLeading = (isLeading == 1 && d == 0) ? 1 : 0;
46            // Still limited only if we were limited and chose the maximal digit
47            int nextLimited = (isLimited == 1 && d == upperBound) ? 1 : 0;
48            count += dfs(index + 1, nextHasZero, nextLeading, nextLimited);
49        }
50
51        // Cache only the unconstrained branch (independent of n's prefix)
52        if (isLimited == 0) {
53            memo[index][hasZero][isLeading][isLimited] = count;
54        }
55        return count;
56    }
57}
58

1class Solution {
2public:
3    long long countDistinct(long long n) {
4        // Convert the upper bound to its decimal string representation.
5        string digits = to_string(n);
6        int length = digits.size();
7
8        // Memoization table indexed by:
9        //   position, hasZero, isLeadingZero, isLimited
10        // Only states with isLimited == false are cached (the limited branch is unique).
11        static long long memo[20][2][2][2];
12        memset(memo, -1, sizeof(memo));
13
14        // Digit DP traversal.
15        //   pos       : current digit index being decided.
16        //   hasZero   : whether a zero has appeared in a non-leading position.
17        //   isLeading  : whether we are still in the leading-zero prefix.
18        //   isLimited  : whether the prefix matches n, restricting the current digit.
19        auto dfs = [&](this auto&& dfs, int pos, int hasZero, int isLeading, int isLimited) -> long long {
20            // Base case: a full number has been formed.
21            // Count it only if it is a genuine number (not all leading zeros)
22            // and it contains at least one zero digit.
23            if (pos == length) {
24                return (hasZero == 1 && isLeading == 0) ? 1 : 0;
25            }
26
27            // Reuse cached results for the free (non-limited) states.
28            if (!isLimited && memo[pos][hasZero][isLeading][isLimited] != -1) {
29                return memo[pos][hasZero][isLeading][isLimited];
30            }
31
32            // Highest digit allowed at this position.
33            int upper = isLimited ? (digits[pos] - '0') : 9;
34            long long result = 0;
35
36            for (int d = 0; d <= upper; ++d) {
37                // A non-leading zero marks the number as containing a zero.
38                int nextHasZero = hasZero || (d == 0 && !isLeading);
39                // Still leading only if we keep placing zeros from the start.
40                int nextLeading = isLeading && d == 0;
41                // Remain limited only if we pick the maximal allowed digit.
42                int nextLimited = isLimited && d == upper;
43                result += dfs(pos + 1, nextHasZero, nextLeading, nextLimited);
44            }
45
46            // Cache the result for non-limited states.
47            if (!isLimited) {
48                memo[pos][hasZero][isLeading][isLimited] = result;
49            }
50            return result;
51        };
52
53        // Start from the most significant digit with leading-zero and limit flags set.
54        return dfs(0, 0, 1, 1);
55    }
56};
57

1/**
2 * Counts how many integers in the range [1, n] contain no digit '0'.
3 * Implemented with digit dynamic programming (digit DP).
4 *
5 * @param n - The upper bound of the range (inclusive).
6 * @returns The count of qualifying integers.
7 */
8function countDistinct(n: number): number {
9    // String form of n, used to access each digit by position.
10    const digits = n.toString();
11    // Total number of digits in n.
12    const length = digits.length;
13
14    // Memoization table indexed by [position][hasZero][isLeading][isTight].
15    // Initialized to -1 to denote "not yet computed".
16    const memo: number[][][][] = Array.from({ length }, () =>
17        Array.from({ length: 2 }, () =>
18            Array.from({ length: 2 }, () => Array(2).fill(-1)),
19        ),
20    );
21
22    /**
23     * Recursively builds the number digit by digit.
24     *
25     * @param position  - Current digit index being chosen.
26     * @param hasZero    - 1 if a digit '0' has already been placed (after leading zeros end).
27     * @param isLeading  - 1 if we are still inside the leading-zero region.
28     * @param isTight    - 1 if the prefix chosen so far equals n's prefix (upper bound constraint active).
29     * @returns The count of valid completions from this state.
30     */
31    const dfs = (
32        position: number,
33        hasZero: number,
34        isLeading: number,
35        isTight: number,
36    ): number => {
37        // Reached the end: valid only if no zero appeared and it is a real (non-empty) number.
38        if (position === length) {
39            return hasZero === 0 && isLeading === 0 ? 1 : 0;
40        }
41
42        // Reuse cached result only when unconstrained by the upper bound (isTight === 0).
43        if (isTight === 0 && memo[position][hasZero][isLeading][isTight] !== -1) {
44            return memo[position][hasZero][isLeading][isTight];
45        }
46
47        // Highest digit we may place: bounded by n's digit when tight, otherwise 9.
48        const upperBound = isTight === 1 ? parseInt(digits[position]) : 9;
49        let count = 0;
50
51        // Try every allowed digit at the current position.
52        for (let digit = 0; digit <= upperBound; digit++) {
53            // hasZero turns on if it was already on, or we place a '0' after leading zeros ended.
54            const nextHasZero =
55                hasZero === 1 || (digit === 0 && isLeading === 0) ? 1 : 0;
56            // Still leading-zero only if we were leading and placed another '0'.
57            const nextLeading = isLeading === 1 && digit === 0 ? 1 : 0;
58            // Remain tight only if we were tight and chose exactly the upper-bound digit.
59            const nextTight = isTight === 1 && digit === upperBound ? 1 : 0;
60
61            count += dfs(position + 1, nextHasZero, nextLeading, nextTight);
62        }
63
64        // Cache the result for the unconstrained (non-tight) state.
65        if (isTight === 0) {
66            memo[position][hasZero][isLeading][isTight] = count;
67        }
68        return count;
69    };
70
71    // Start from position 0, no zero yet, inside leading zeros, and tight against n.
72    return dfs(0, 0, 1, 1);
73}
74

Time and Space Complexity

Time Complexity: O(log₁₀ n × D)

The analysis proceeds as follows:

Let s = str(n), so the length of s is O(log₁₀ n), representing the number of digits in n.
The recursion uses @cache to memoize states based on the parameters (i, zero, lead, lim).
- i ranges over O(log₁₀ n) positions.
- zero, lead, and lim are boolean flags, contributing only a constant factor of distinct states.
Therefore, the number of distinct states is O(log₁₀ n).
For each state, the loop iterates over up + 1 possible digit choices, where up is at most 9. This contributes a factor of D, the count of digits from 0 to 9 (i.e., D = 10).
Combining the number of states with the per-state work gives a total time complexity of O(log₁₀ n × D).

Space Complexity: O(log₁₀ n)

The analysis proceeds as follows:

The memoization cache stores O(log₁₀ n) distinct states (since the boolean flags only contribute a constant factor).
The recursion depth is bounded by the length of s, which is O(log₁₀ n), contributing to the call stack.
Hence, the overall space complexity is O(log₁₀ n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing leading zeros with "real" zeros

The most common mistake is treating every 0 digit as a forbidden zero, including the zeros in the leading-zero prefix. This conflates two very different situations:

A 0 placed before any significant digit (e.g., the conceptual 007 that represents 7) is just a placeholder and must not disqualify the number.
A 0 placed after a significant digit (e.g., the 0 in 70) is a real zero and should disqualify the number.

If you write the transition as:

# WRONG: treats leading zeros as real zeros
next_has_zero = has_zero or (digit == 0)

then numbers like 7 (built as 007 when n has 3 digits) get marked as containing a zero and are incorrectly excluded, producing a count that is far too small.

Solution. Gate the zero check with not is_leading, so a zero only counts once the number has actually started:

next_has_zero = has_zero or (digit == 0 and not is_leading)

Pitfall 2: Counting the empty number (zero) as valid

At the base case, it is tempting to return 1 whenever not has_zero:

# WRONG: counts the all-zeros construction (the number 0) as valid
if index >= len(s):
    return 1 if not has_zero else 0

But if every digit chosen was a leading zero, the constructed number is 0, which lies outside the range [1, n]. Forgetting the is_leading guard inflates the count by exactly one (the spurious 0).

Solution. Require that the number has actually started before counting it:

if index >= len(s):
    return 1 if (not has_zero and not is_leading) else 0

Pitfall 3: Including `is_leading` and `is_limit` in the memoized state without care

@cache keys on all four arguments. This is correct here, but a subtle performance pitfall arises if you try to "optimize" by dropping is_limit from the cache. States where is_limit=True are tied to a specific prefix of n and visited at most once per position, while is_limit=False states are the reusable ones. Mixing them under the same key (e.g., by omitting is_limit) causes incorrect counts, because a tight state and a free state at the same position have genuinely different answers.

Solution. Keep all relevant flags in the cache key, as the given code does. If you want to reduce cache pressure, only memoize the fully-free branch (is_leading=False and is_limit=False), but do not silently drop a flag that changes the result:

# Safe pattern: memoize only the reusable, unconstrained sub-states
@cache
def dfs_free(index, has_zero):
    ...  # only valid when not leading and not limited

Pitfall 4: Off-by-one in the digit upper bound

Using range(upper) instead of range(upper + 1) silently drops the boundary digit:

for digit in range(upper):   # WRONG: misses digit == upper

This excludes valid numbers that match n's prefix exactly (for instance, n itself), undercounting the result.

Solution. Iterate inclusively with range(upper + 1) so the tight boundary digit is considered, and so the next_is_limit = is_limit and digit == upper transition can ever fire.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering