Is Check if Number is a Sum of Powers of Three easy or hard?

The problem is rated Medium because the optimal solution depends on recognizing the base-3 property. Without that insight, many candidates attempt subset generation or recursion, which is more complex and less efficient.

Check if Number is a Sum of Powers of Three Python/Java solution

The typical implementation uses a loop: while n > 0, check if n % 3 equals 2. If so return false; otherwise divide n by 3 and continue. This logic is identical across Python, Java, C++, C#, and JavaScript and runs in O(log n) time.

How to solve Check if Number is a Sum of Powers of Three in O(log n)?

Use the base-3 observation. Convert the number by repeatedly computing n % 3 and n / 3. If any remainder equals 2, return false because it implies a power of three must be used more than once. If all digits are 0 or 1, the number is a valid sum of distinct powers of three.

What is the best approach for Check if Number is a Sum of Powers of Three?

The optimal approach checks the base-3 representation of the number. If any digit equals 2, the number requires using the same power of three twice, which is not allowed. By repeatedly dividing n by 3 and checking remainders, you solve the problem in O(log n) time and O(1) space.

Is Check if Number is a Sum of Powers of Three asked at Google/Amazon/Meta?

Problems based on number representation and greedy reasoning frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests mathematical insight and the ability to recognize patterns in number bases, which is a common interview theme.

What data structure is used in Check if Number is a Sum of Powers of Three?

The optimal solution does not require any data structure. It relies purely on arithmetic operations and base-3 digit checks. The alternative backtracking approach may use recursion stacks or arrays storing powers of three.

What is the time complexity of Check if Number is a Sum of Powers of Three?

The optimal greedy solution runs in O(log n) time because the number is repeatedly divided by 3 until it becomes zero. Space complexity is O(1). A brute-force backtracking approach explores subsets of powers of three and takes O(2^k) time where k is about log3(n).

Description Hints 2 Solution Video 20:08

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

Medium79.4% acceptance4 companies

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

An integer y is a power of three if there exists an integer x such that y == 3^x.

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 3¹ + 3²

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 3⁰ + 3² + 3⁴

Example 3:

Input: n = 21
Output: false

Constraints:

1 <= n <= 10⁷

Asked at 4 companies

Google Bloomberg Amazon Meta

Topics

Math

Hints open one at a time

Hint 1

Let's note that the maximum power of 3 you'll use in your soln is 3^16

Hint 2

The number can not be represented as a sum of powers of 3 if it's ternary presentation has a 2 in it

20:08

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution