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.
Example 1:
Input: n = 10
Output: 9
Explanation:
The integers we wrote down are 1, 2, 3, 4, 5, 6, 7, 8, 9, 1. There are 9 distinct integers (1, 2, 3, 4, 5, 6, 7, 8, 9).
Example 2:
Input: n = 3
Output: 3
Explanation:
The integers we wrote down are 1, 2, 3. There are 3 distinct integers (1, 2, 3).
Constraints:
1 <= n <= 1015Problem Overview: You iterate through integers in a range and remove every digit 0 from their decimal representation. Different original numbers can collapse to the same value after zeros are removed. The task is to count how many distinct integers remain after this transformation.
Approach 1: Brute Force Simulation (O(n · d) time, O(n) space)
The direct idea is to iterate from 1 to n, convert each number to a string, remove every '0', then convert the remaining digits back to an integer. Store the result in a hash set to keep only unique values. If the number becomes an empty string, treat it as 0. The complexity depends on the number of digits d per integer, so the runtime becomes O(n · d) with O(n) space for the set. This works only for small ranges because n can be large.
Approach 2: Digit DP (O(d · 10 · states) time, O(states) space)
Instead of enumerating every number, use Digit Dynamic Programming to generate the resulting integers formed after removing zeros. While processing digits from most significant to least significant, the DP keeps track of the current position, tight bound with the original number, and whether the resulting number has started forming. Whenever a digit other than 0 appears, it contributes to the constructed integer; zeros are skipped. The key observation: many original numbers map to the same compressed value once zeros disappear, so the DP counts unique constructed results instead of all source numbers.
The DP state typically includes (pos, tight, started). Transition through digits 0-9; when the digit is 0, it does not extend the resulting number. Non‑zero digits append to the result. Memoization avoids recomputation for identical states, reducing the complexity to roughly O(d · 10 · states), where d is the number of digits in the bound.
This technique is common in problems where digit transformations create many collisions between numbers. Digit DP efficiently explores the valid space without enumerating all integers. If you want to strengthen this pattern, review related topics such as Dynamic Programming, Math, and specialized Digit DP state design.
Recommended for interviews: Start by explaining the brute force mapping from each integer to its zero‑stripped version to demonstrate understanding. Then move to the Digit DP optimization. Interviewers typically expect the DP insight for large constraints because it avoids iterating through every integer and shows strong control over digit‑level state transitions.
The problem essentially asks us to count the number of integers in the range [1, n] that do not contain the digit 0. We can solve this problem using digit DP.
We design a function dfs(i, zero, lead, limit), which represents the number of valid solutions when we are currently processing the i-th digit of the number. We use zero to indicate whether a non-zero digit has appeared in the current number, lead to indicate whether we are still processing leading zeros, and limit to indicate whether the current number is constrained by the upper bound. The answer is dfs(0, 0, 1, 1).
In the function dfs(i, zero, lead, limit), if i is greater than or equal to the length of the number, we can check zero and lead. If zero is false and lead is false, it means the current number does not contain 0, so we return 1; otherwise, we return 0.
For dfs(i, zero, lead, limit), we can enumerate the value of the current digit d, then recursively calculate dfs(i+1, nxt_zero, nxt_lead, nxt_limit), where nxt_zero indicates whether a non-zero digit has appeared in the current number, nxt_lead indicates whether we are still processing leading zeros, and nxt_limit indicates whether the current number is constrained by the upper bound. If limit is true, then up is the upper bound of the current digit; otherwise, up is 9.
The time complexity is O(log_{10} n times D) and the space complexity is O(log_{10} n), where D represents the count of digits from 0 to 9.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation with Hash Set | O(n · d) | O(n) | Small ranges where iterating every integer is feasible |
| Digit DP | O(d · 10 · states) | O(states) | Large constraints where many numbers map to the same value after removing zeros |
Count Distinct Integers After Removing Zeros | Leetcode 3747 | Weekly Contest 476 • Sanyam IIT Guwahati • 2,442 views views
Watch 6 more video solutions →Practice Count Distinct Integers After Removing Zeros with our built-in code editor and test cases.
Practice on FleetCode