Find the N-th Positive Integer Whose Digits Are All 3, 5 or 6
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Call a positive integer a **good number** if every one of its decimal digits is 3, 5 or 6. Listed in increasing order, the good numbers are:
`3, 5, 6, 33, 35, 36, 53, 55, 56, 63, 65, 66, 333, 335, 336, ...`
so the 1st good number is 3, the 4th is 33, the 7th is 53 and the 13th is 333. Given `n`, return the `n`-th good number.
### Function Signature
```python
def nth_good_number(n: int) -> str:
```
### Rules
- `n` is 1-indexed: `n = 1` asks for the smallest good number.
- Return the number as a decimal string with no leading zeros or other characters, because for large `n` it exceeds the range of 64-bit integers.
### Constraints
- `1 <= n <= 10^12`
- The answer has at most 25 digits.
### Examples
**Example 1**
- Input: `n = 7`
- Output: `"53"`
- Explanation: The list begins `3, 5, 6, 33, 35, 36, 53`.
**Example 2**
- Input: `n = 13`
- Output: `"333"`
- Explanation: There are 3 one-digit and 9 two-digit good numbers, so the 13th is the smallest three-digit one.
**Example 3**
- Input: `n = 100`
- Output: `"6363"`
- Explanation: There are 3 + 9 + 27 = 39 good numbers with at most three digits, so the 100th is the 61st four-digit good number.
Overview: Positive integers whose digits are only 3, 5 or 6 are called good numbers; return the n-th good number in increasing order as a string for n up to one trillion. Tests counting by digit length and mapping the rank to a base-3 style digit sequence.