Skip to main content
Talentd

Count Distinct Integers After Removing Zeros - Solution & Explanation

MediumMathDynamic Programming13 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 1015

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Simulation with Hash SetO(n · d)O(n)Small ranges where iterating every integer is feasible
Digit DPO(d · 10 · states)O(states)Large constraints where many numbers map to the same value after removing zeros

Video Solution

Count Distinct Integers After Removing Zeros | Leetcode 3747 | Weekly Contest 476 • Sanyam IIT Guwahati • 2,542 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Count Distinct Integers After Removing Zeros easy or hard?
The problem is rated Medium because the transformation seems simple but counting unique outcomes efficiently requires Digit DP. Brute force works conceptually but fails for large inputs, so recognizing the digit‑state optimization is the key challenge.
Count Distinct Integers After Removing Zeros Python/Java solution
Most implementations use Digit DP with recursion or iterative DP plus memoization. The same logic works across Python, Java, C++, Go, and TypeScript: process digits, maintain tight bounds, skip zero digits when constructing the result, and memoize states for efficiency.
What is the best approach for Count Distinct Integers After Removing Zeros?
Digit Dynamic Programming is the most efficient approach for large constraints. Instead of checking every number, the algorithm processes digits from most significant to least significant and skips zero digits while constructing the resulting integer. This avoids enumerating all values and reduces the complexity to roughly O(d · 10 · states).
Is Count Distinct Integers After Removing Zeros asked at Google/Amazon/Meta?
Problems involving digit transformations and Digit DP frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often ask for counting numbers with specific digit constraints or transformations, making this problem good practice for those interview patterns.
What data structure is used in Count Distinct Integers After Removing Zeros?
The optimized solution relies on memoization tables for Digit DP states. In simpler brute force implementations, a hash set is used to store distinct integers after removing zeros from each number.
What is the time complexity of Count Distinct Integers After Removing Zeros?
The optimal Digit DP solution runs in about O(d · 10 · states), where d is the number of digits in the upper bound. Each digit position tries digits 0–9 while memoizing repeated states. A naive brute force approach would take O(n · d) time because it processes every integer individually.
How to solve Count Distinct Integers After Removing Zeros in O(d · 10) style complexity?
Model the problem with Digit DP. Process the digits of the upper bound while tracking position, tight constraint with the bound, and whether a non‑zero digit has started the resulting number. When a digit is zero, skip it instead of appending. Memoize states to avoid recomputation and count only unique constructed integers.

Ready to solve this problem?

Practice Count Distinct Integers After Removing Zeros with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer