LeetCode 1780. Check if Number is a Sum of Powers of Three Solution in Java, C++, Python & More | Explanation + Code

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 == 3x.

 

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 31 + 32

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 30 + 32 + 34

Example 3:

Input: n = 21
Output: false

 

Constraints:

• 1 <= n <= 107

Solutions

Solution 1: Mathematical Analysis

We find that if a number n can be expressed as the sum of several "different" powers of three, then in the ternary representation of n, each digit can only be 0 or 1.

Therefore, we convert n to ternary and then check whether each digit is 0 or 1. If not, then n cannot be expressed as the sum of several powers of three, and we directly return false; otherwise, n can be expressed as the sum of several powers of three, and we return true.

The time complexity is O(log_3 n), and the space complexity is O(1).

PythonJavaC++GoTypeScriptRustC#

class Solution: def checkPowersOfThree(self, n: int) -> bool: while n: if n % 3 > 1: return False n //= 3 return True(code-box)

class Solution { public boolean checkPowersOfThree(int n) { while (n > 0) { if (n % 3 > 1) { return false; } n /= 3; } return true; } }(code-box)

class Solution { public: bool checkPowersOfThree(int n) { while (n) { if (n % 3 > 1) return false; n /= 3; } return true; } };(code-box)

func checkPowersOfThree(n int) bool { for n > 0 { if n%3 > 1 { return false } n /= 3 } return true }(code-box)

function checkPowersOfThree(n: number): boolean { while (n) { if (n % 3 > 1) return false; n = Math.floor(n / 3); } return true; }(code-box)

impl Solution { pub fn check_powers_of_three(n: i32) -> bool { let mut n = n; while n > 0 { if n % 3 > 1 { return false; } n /= 3; } true } }(code-box)

public class Solution { public bool CheckPowersOfThree(int n) { while (n > 0) { if (n % 3 > 1) { return false; } n /= 3; } return true; } }(code-box)