Formatted question description: https://leetcode.ca/all/1780.html

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

## Level

Medium

## Description

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^1 + 3^2

**Example 2:**

**Input:** n = 91

**Output:** true

**Explanation:** 91 = 3^0 + 3^2 + 3^4

**Example 3:**

**Input:** n = 21

**Output:** false

**Constraints:**

`1 <= n <= 10^7`

## Solution

The integer `n`

can always be converted into a base three representation. Each digit in base three representation is 0, 1 or 2. To represent `n`

as the sum of distinct powers of three, each digit in base three representation must be 0 or 1.

In this problem, we do not actually convert `n`

into a base three representation. We only need to calculate the digits and we do not care the order of the digits. Therefore, while `n > 0`

, calculate the `n % 3`

each time and if a remainder 2 is found, return `false`

. Otherwise, let `n = n / 3`

and repeat the process until `n`

becomes 0. If `n`

becomes 0 without any remainder 2 met, return `true`

.

```
class Solution {
public boolean checkPowersOfThree(int n) {
while (n > 0) {
int remainder = n % 3;
if (remainder == 2)
return false;
n /= 3;
}
return true;
}
}
```