Last Updated: 28 Mar, 2026

Distinct Integers After Zero Removal

Moderate
Asked in company
Hummingbird web Solutions

Problem statement

You are given a positive integer n. For every integer x in the inclusive range [1, n], we perform an operation: create a new integer by removing all the 0 digits from the decimal representation of x.


For example:

If x = 102, the new integer is 12.
If x = 200, the new integer is 2.
If x = 198, the new integer is 198.


Your task is to find the total number of distinct integers that are generated by applying this operation to every integer from 1 to n.


Input Format:
The first and only line of input contains a single integer n.


Output Format:
Your function should return a single integer representing the count of distinct integers. The runner code will handle printing.


Notes:
The constraint on n (<= 10^15) makes a brute-force simulation impossible. The key insight is that this problem is equivalent to counting the number of positive integers up to n that do not contain the digit '0'. This is because any number y without a '0' can be generated from x=y, and any number y > n cannot be generated from any x <= n (since removing zeros only makes a number smaller or equal).