1422. Distinct Powers Sum
A scale comes with weights of mass 1, k, k2, k3 and so on, with exactly one weight of each mass, and it can only be loaded by putting weights on one pan. Given the target mass n and the base k, return true if n can be written as a sum of distinct powers of k (each power used at most once), and false otherwise. Equivalently, every digit of n written in base k must be 0 or 1. Repeated division by k gives O(log n) time and O(1) extra space.
Example 1
- Input:
- n = 13, k = 3
- Output:
- true
- Explanation:
13 = 9 + 3 + 1, which is 111 in base 3, so every digit is 0 or 1.
Example 2
- Input:
- n = 5, k = 3
- Output:
- false
- Explanation:
5 is 12 in base 3 and contains the digit 2, so no choice of distinct powers works.
Constraints
1 ≤ n ≤ 1015
2 ≤ k ≤ 109
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_k n)
- Space
- O(1)