Check if Number is a Sum of Powers of Three

Given an integer n, determine whether it can be expressed as the sum of distinct powers of three. This is equivalent to checking whether the base-3 representation contains only digits 0 and 1.

Input Format

n = positive integer

Output Format

true if n can be represented as a sum of distinct powers of three

Constraints

  • 1 <= n <= 10^7

Examples

Example 1:

Input:

n = 12

Output:

true

Explanation:

12 = 9 + 3.

Example 2:

Input:

n = 21

Output:

false

Explanation:

21 in base 3 contains a digit 2, so it is not valid.

Loading...
Check if Number is a Sum of Powers of Three