Watch 7 video solutions for Count Distinct Integers After Removing Zeros, a medium level problem involving Math, Dynamic Programming. This walkthrough by Sanyam IIT Guwahati has 2,442 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |