4054. Count Distinct Integers After Removing Zeros
My accepted Python solution to LeetCode problem 4054, Count Distinct Integers After Removing Zeros, running in 3ms.
- Difficulty: Medium
- Python
- Runtime 3ms
- Memory 17.2MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 3ms, memory 17.2MB, accepted 2025-12-30.
class Solution:
def countDistinct(self, n: int) -> int:
# Count numbers from 1 to n that have no zeros
# These are exactly the distinct values we can get
# because:
# 1. Numbers without zeros map to themselves
# 2. Numbers with zeros map to smaller numbers without zeros
# (which are already counted in the first group)
# A number without zeros has all digits from {1-9}
# We need to count how many such numbers exist from 1 to n
# Use digit DP
s = str(n)
d = len(s)
# Count all numbers with fewer digits (1 to d-1 digits) that have no zeros
count = sum(9 ** i for i in range(1, d))
# Count d-digit numbers without zeros that are <= n
# Use digit DP approach
for i, ch in enumerate(s):
digit = int(ch)
remaining = d - i - 1
if digit == 0:
# Current digit is 0, which is not allowed in "no zeros" numbers
# So we can't form any valid number with digits up to here matching
# All valid numbers must have been counted in smaller prefix cases
break
else:
# Count numbers where this position has digit 1 to digit-1
# and remaining positions can be 1-9
if i == 0:
# First digit: can be 1 to digit-1
count += (digit - 1) * (9 ** remaining)
else:
# Non-first digit: can be 1 to digit-1 (not 0)
count += (digit - 1) * (9 ** remaining)
else:
# If we completed the loop, n itself has no zeros, so add 1
count += 1
return count