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.
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.
Implement `nth_good_number(n)`, which returns the `n`-th good number.
**Rules**
- `n` is 1-indexed: `n = 1` asks for the smallest good number.
- Return the answer as a decimal string with no leading zeros, signs, spaces or other characters. For large `n` the answer exceeds the range of 64-bit integers, so it must be returned as a string.
- `n` itself can exceed 2^31 - 1, so it needs a 64-bit integer type (`long` in Java, `long long` in C++).
**Constraints**
- `1 <= n <= 10^12`
- The answer has at most 25 digits.
**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.
Constraints
- 1 <= n <= 10^12
- n can exceed 2^31 - 1, so use a 64-bit integer type for n
- The answer has at most 25 digits and is returned as a string
Examples
Input: (1,)
Expected Output: "3"
Explanation: Minimum n (singleton/minimum case): the smallest good number.
Input: (2,)
Expected Output: "5"
Explanation: Second one-digit good number.
Hints
- How many good numbers have exactly L digits? Use that count to work out how many digits the n-th one has.
- Among good numbers of the same length, the order 3 < 5 < 6 behaves like the digits 0 < 1 < 2. What number system does that suggest?
- Subtracting 1 before taking each remainder lets you handle all lengths at once without computing the length first.
Community answers
Answer by fijeijfakdknjkvl
def nth_good_number(n: int) -> str:
digits = ["3", "5", "9"]
result = []
while n > 0:
n -= 1
result.append(digits[n % 3])
n //= 3
return ''.join(reversed(result))