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;
    }
}

All Problems

All Solutions