Distinct Integers After Zero Removal

Moderate

0/80

0 upvote

Asked in company

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

For x from 1 to 9, the generated numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9.

For x = 10, removing the '0' gives 1.

The set of distinct integers generated is {1, 2, 3, 4, 5, 6, 7, 8, 9}. The size of this set is 9.

Sample Input 2:

Sample Output 2:

Explanation for Sample 2:

This is equivalent to counting numbers from 1 to 100 that do not contain '0'.

1-digit numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9 (9 numbers).
2-digit numbers: Numbers from 11 to 99 that do not contain '0'. There are 9 * 9 = 81 such numbers (e.g., 11..19, 21..29, ..., 91..99).
3-digit numbers: The only number is 100, which contains a '0'.
Total count = 9 + 81 = 90.

Expected Time Complexity:

The expected time complexity is O(logN).

Constraints:

1 <= n <= 10^15
Time Limit: 1 sec

Approaches (1)

Approach 1

Dynamic Programming

Time Complexity

Space Complexity

(100% EXP penalty)

Distinct Integers After Zero Removal

Console