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.

Description Hints 2 Solution Video 26:46

3747. Count Distinct Integers After Removing Zeros

Medium23.1% acceptance1 company

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 <= 10¹⁵

Asked at 1 company

Google

Topics

Dynamic Programming Math

Hints open one at a time

Hint 1

Build integers less than or equal to n using only digits from 1 to 9

Hint 2

Count such integers using math or digit DP

26:46

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countDistinct(self, n: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution