Determine whether a positive integer can be written as a sum of distinct powers of three.
Problem
Given an integer n, decide whether it can be represented as a sum of distinct powers of three.
A number is valid if it can be written in the form:
where all exponents are different.
Return true if such a representation exists, otherwise return false.
Intuition
Each power of three may be used at most once. The task is equivalent to checking whether the base-3 representation of n contains only digits 0 or 1.
Input Format
- A single integer
n.
Output Format
- Return
trueifncan be expressed as a sum of distinct powers of three; otherwise returnfalse.
Constraints
1 <= n <= $10^{7}$- Powers of three must be distinct.
Example 1
Input
n = 12
Output
true
Explanation
12 = 9 + 3 = ^1, so it is a sum of distinct powers of three.
Example 2
Input
n = 21
Output
false
Explanation
The ternary representation of 21 is 210, which contains a digit 2. That means it cannot be formed using each power of three at most once.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.