1831. Balanced Ternary Writer
An old computer stores numbers in balanced ternary, which uses three digits: 1 for +1, 0 for 0 and T for -1. The digit at distance k from the right is multiplied by 3^k and all the products are added. Every integer, positive or negative, has exactly one such form with no leading zeros, and no separate minus sign is needed.
Given the integer n, return it written in balanced ternary, most significant digit first. For example, 8 is 10T because 9 + 0 - 1 = 8. The value 0 is written as 0. Aim for O(log n) time. Take care with negative numbers, since the remainder operator behaves differently for them in different languages.
Example 1
- Input:
- n = 8
- Output:
- "10T"
- Explanation:
9 + 0 - 1 = 8, so the digits are 1, 0, T.
Example 2
- Input:
- n = -8
- Output:
- "T01"
- Explanation:
-9 + 0 + 1 = -8, which mirrors the form of 8 with 1 and T swapped.
Example 3
- Input:
- n = 0
- Output:
- "0"
- Explanation:
Zero is a single 0.
Constraints
-1015 ≤ n ≤ 1015
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(log n)