Counting Without Nines

Hard

A superstitious counter skips every number whose decimal form contains the digit 9. It counts from one: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, …, 18, 20, … Given pos, return the number this counter says at position pos (counting from one), as a string with its decimal digits.

Example 1

pos=12 → '13'

The count goes 1, 2, …, 8, 10, 11, 12, 13: 9 is skipped, so the 12th number is "13".

Example 2

pos=81 → '100'

9, 19, …, 89 and all of 90–99 are skipped, so the 80th number is 88 and the very next one is "100".

Example 3

pos=3 → '3'

Constraints

1 ≤ pos ≤ 8 · 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math

Similar problems

The K-th Ordering of Digits Hard Stars on One Straight Line Hard Plus-Minus Calculator With Brackets Hard How Many Ones Are Written Hard Amount in Words Hard

Input

pos=12

Expected

'13'

Run checks the first 3 tests in your browser. Submit checks all 60 tests on the server, hidden ones included.