Distinct Powers of Three

Medium

You are given an integer n. Return True if n can be written as a sum of **distinct** powers of three (1, 3, 9, 27, …, each used at most once), and False otherwise.

Example 1

n=31 → True

31 = 27 + 3 + 1 = 3³ + 3¹ + 3⁰.

Example 2

n=15 → False

15 = 9 + 3 + 3, but 3 cannot be used twice, and there is no other way.

Example 3

n=1 → True

1 = 3⁰.

Constraints

1 ≤ n ≤ 10⁷

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math

Similar problems

Adding Digit Lists Medium Backwards Digits in 32 Bits Medium Number in Roman Numerals Medium Division Without Dividing Medium Multiplying Digit Strings Medium

Input

n=31

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.