Find the N-th Positive Integer Whose Digits Are All 3, 5 or 6

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

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.

N-th Number Built from Digits 3, 5 and 6

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.

Hints

1. How many good numbers have exactly L digits? Use that count to work out how many digits the n-th one has.
2. 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?
3. Subtracting 1 before taking each remainder lets you handle all lengths at once without computing the length first.

Approach

There are 3^L good numbers with exactly L digits, and all shorter good numbers come before all longer ones. Within one length, mapping 3 -> 0, 5 -> 1, 6 -> 2 turns increasing numeric order into increasing base-3 order, so the sequence is exactly bijective base 3 (digits 1..3 instead of 0..2). The reference repeatedly decrements n, takes (n mod 3) as the least significant digit (0 -> '3', 1 -> '5', 2 -> '6'), and divides by 3, until n reaches 0; then it reverses the collected digits. For example n = 7: 6 mod 3 = 0 gives '3', n becomes 2; 1 mod 3 = 1 gives '5', n becomes 0; reversed, the answer is "53". All intermediate values stay at or below n <= 10^12, which fits a 64-bit integer and is exact in a JavaScript number, while the answer itself (up to 25 digits) is built as a string.

• Time complexity: O(log n)
• Space complexity: O(log n)