Check if Number is a Sum of Powers of Three solution and explanation
Google
9 more videos on this problem
Check if Number is a Sum of Powers of Three - Leetcode 1780 - PythonNeetCodeIO · 20:08 · 11K views
Check if Number is a Sum of Powers of Three | Maths Proof | 3 Ways | Leetcode 1780 |codestorywithMIKcodestorywithMIK · 41:28 · 7K views
Check if Number is a Sum of Powers of Three | Leetcode 1780Techdose · 10:58 · 4K views
1780. Check if Number is a Sum of Powers of ThreeFraz · 3:06 · 4K views
Leetcode 1780. Check if Number is a Sum of Powers of Three #Leetcode #1780 #powers of threeCode with Alisha · 12:33 · 3K views
1780. Check if Number is a Sum of Powers of Three | leetcode daily challenge | faang | shashcodeShashCode · 6:44 · 2K views
Check if Number is a Sum of Powers of Three | LeetCode 1780 | Coders CampCoders Camp · 2:55 · 1K views
LeetCode 1780. Check if Number is a Sum of Powers of Three | Medium | Biweekly Contest 47 | Algo ExpCherry Coding [IIT-G] · 5:30 · 1K views
1780. Check if Number is a Sum of Powers of Three (Leetcode Medium)Programming Live with Larry · 4:46 · 881 views
Daily Leetcode #1799: Mar 04, 2025 - 1780. Check if Number is a Sum of Powers of ThreeProgramming Live with Larry · 9:27 · 347 views
The problem
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
Approach overview
Problem Overview: You receive an integer n. The task is to determine whether it can be represented as the sum of distinct powers of three (for example 1, 3, 9, 27...). Each power can be used at most once. The problem reduces to checking whether a combination of these powers adds exactly to n.
Approach 1: Greedy / Base-3 Representation (Time: O(log3 n), Space: O(1))
The key observation: powers of three behave like digits in base-3 representation. If n can be written as a sum of distinct powers of three, then its base-3 representation must contain only digits 0 or 1. A digit 2 would mean the same power of three is used twice, which violates the constraint. Convert the number by repeatedly dividing n by 3 and checking the remainder. If any remainder equals 2, return false. Otherwise continue until n becomes zero. This greedy observation avoids generating combinations entirely and runs in logarithmic time. The approach relies purely on number properties from math and is the optimal solution expected in interviews.
Approach 2: Backtracking Over Powers (Time: O(2k), Space: O(k))
Another way to think about the problem is as a subset-sum over powers of three. First generate powers of three up to n (for example 1, 3, 9, 27...). Then recursively try including or excluding each power while subtracting from the remaining target. If the remaining value reaches 0, a valid combination exists. If it becomes negative or you exhaust all powers, that branch fails. This approach uses recursion and explores the decision tree of subsets, which is why the complexity becomes exponential in the number of powers (k ≈ log3 n). It demonstrates the brute-force reasoning behind the problem and uses techniques from backtracking and recursion.
Recommended for interviews: The greedy base-3 check is the expected solution. Interviewers want to see the insight that the sum of distinct powers of three corresponds directly to base-3 digits restricted to 0 and 1. Implementing the greedy division loop shows strong mathematical reasoning and yields O(log n) time with constant space. The backtracking approach is still useful to discuss because it shows how the problem maps to subset selection before the mathematical shortcut is recognized.
Approach 1: Greedy Approach
This approach involves checking if the remainder when dividing by 3 is other than 0 or 1, and subtracting the corresponding power of three if it is 1. Repeat this until the number reduces to zero or we find a remainder that isn't suitable.
def check_powers_of_three(n: int) -> bool:
while n > 0:
if n % 3 == 2:
return False
n //= 3
return True
n = 12
print(check_powers_of_three(n))class Solution {
public boolean checkPowersOfThree(int n) {
while (n > 0) {
if (n % 3 == 2) return false;
n /= 3;
}
return true;
}
public static void main(String[] args) {
Solution sol = new Solution();
int n = 12;
System.out.println(sol.checkPowersOfThree(n));
}
}#include <iostream>
bool checkPowersOfThree(int n) {
while (n > 0) {
if (n % 3 == 2)
return false;
n /= 3;
}
return true;
}
int main() {
int n = 12;
std::cout << (checkPowersOfThree(n) ? "true" : "false") << std::endl;
return 0;
}function checkPowersOfThree(n) {
while (n > 0) {
if (n % 3 === 2) return false;
n = Math.floor(n / 3);
}
return true;
}
const n = 12;
console.log(checkPowersOfThree(n));#include <stdbool.h>
#include <stdio.h>
bool checkPowersOfThree(int n) {
while (n > 0) {
if (n % 3 == 2)
return false;
n /= 3;
}
return true;
}
int main() {
int n = 12;
printf("%s\n", checkPowersOfThree(n) ? "true" : "false");
return 0;
}using System;
class Solution {
public bool CheckPowersOfThree(int n) {
while (n > 0) {
if (n % 3 == 2)
return false;
n /= 3;
}
return true;
}
static void Main(string[] args) {
Solution sol = new Solution();
int n = 12;
Console.WriteLine(sol.CheckPowersOfThree(n));
}
}The Python solution checks each digit in the ternary representation of n. If digit is 2, return false, otherwise n is reduced by division.
Time Complexity: O(log3n).
Space Complexity: O(1).
Approach 2: Backtracking Approach
This approach uses recursion to try all combinations of the power of threes by backtracking. It searches incrementally and backs out when a wrong path is reached.
def check_powers_of_three(n: int, power: int = 0) -> bool:
if n == 0:
return True
if n < 3 ** power:
return False
return (check_powers_of_three(n - 3 ** power, power + 1) or
check_powers_of_three(n, power + 1))
n = 12
print(check_powers_of_three(n))class Solution {
private boolean isSum(int n, int i) {
if (n == 0) return true;
if (n < (int)Math.pow(3, i)) return false;
return isSum(n - (int)Math.pow(3, i), i + 1) || isSum(n, i + 1);
}
public boolean checkPowersOfThree(int n) {
return isSum(n, 0);
}
public static void main(String[] args) {
Solution sol = new Solution();
int n = 12;
System.out.println(sol.checkPowersOfThree(n));
}
}#include <iostream>
#include <cmath>
bool isSum(int n, int i) {
if (n == 0) return true;
if (n < std::pow(3, i)) return false;
return isSum(n - int(std::pow(3, i)), i + 1) || isSum(n, i + 1);
}
bool checkPowersOfThree(int n) {
return isSum(n, 0);
}
int main() {
int n = 12;
std::cout << (checkPowersOfThree(n) ? "true" : "false") << std::endl;
return 0;
}function checkPowersOfThree(n, power = 0) {
if (n === 0) return true;
if (n < 3 ** power) return false;
return checkPowersOfThree(n - 3 ** power, power + 1) ||
checkPowersOfThree(n, power + 1);
}
const n = 12;
console.log(checkPowersOfThree(n));#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool isSum(int n, int i) {
if (n == 0) return true;
if (n < pow(3, i)) return false;
return isSum(n - (int)pow(3, i), i + 1) || isSum(n, i + 1);
}
bool checkPowersOfThree(int n) {
return isSum(n, 0);
}
int main() {
int n = 12;
printf("%s\n", checkPowersOfThree(n) ? "true" : "false");
return 0;
}using System;
class Solution {
private bool IsSum(int n, int i) {
if (n == 0) return true;
if (n < Math.Pow(3, i)) return false;
return IsSum(n - (int)Math.Pow(3, i), i + 1) || IsSum(n, i + 1);
}
public bool CheckPowersOfThree(int n) {
return IsSum(n, 0);
}
static void Main(string[] args) {
Solution sol = new Solution();
int n = 12;
Console.WriteLine(sol.CheckPowersOfThree(n));
}
}Python employs recursion, checking each power of three as part of the sum and reducing the problem incrementally.
Time Complexity: Exponential
Space Complexity: O(n) due to recursion depth.
Approach 3: 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).
function checkPowersOfThree(n: number): boolean {
while (n) {
if (n % 3 > 1) return false;
n = Math.floor(n / 3);
}
return true;
}func checkPowersOfThree(n int) bool {
for n > 0 {
if n%3 > 1 {
return false
}
n /= 3
}
return true
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(log3n). |
| Backtracking Approach | Time Complexity: Exponential |
| Mathematical Analysis | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy / Base-3 Representation | O(log n) | O(1) | Best general solution. Uses number properties to check digits in base-3. |
| Backtracking Over Powers | O(2^k), k ≈ log3(n) | O(k) | Useful for understanding the subset-sum formulation or during initial brute-force reasoning. |
Frequently asked questions
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).