Check if Number is a Sum of Powers of Three

Check if Number is a Sum of Powers of Three - Problem

Math Medium

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.

Note: Each power of three can be used at most once in the sum.

Input & Output

Example 1 — Basic Case

$ Input: n = 12

› Output: true

💡 Note: 12 can be represented as 9 + 3, both are distinct powers of three (3² + 3¹)

Example 2 — Impossible Case

$ Input: n = 91

› Output: false

💡 Note: 91 in base-3 is 10101, but this would require using some powers twice which violates the distinct constraint

Example 3 — Single Power

$ Input: n = 21

› Output: false

💡 Note: 21 in base-3 is 210, contains digit 2 which means we'd need the same power twice

Constraints

1 ≤ n ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n = 12

Process

Convert to base-3 and check digits

Output

Return true if valid

Key Takeaway

🎯 Key Insight: A number can be sum of distinct powers of 3 iff its base-3 representation has only 0s and 1s

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that a number can be expressed as sum of distinct powers of 3 if and only if its base-3 representation contains only digits 0 and 1. Best approach is base-3 conversion. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Base-3 Representation	O(log n)	O(1)	Convert number to base-3 and check if all digits are 0 or 1
Greedy Approach	O(log n)	O(1)	Always pick the largest possible power of three first
Brute Force - Generate All Subsets	O(2^k)	O(k)	Generate all possible subsets of powers of three and check if any sum equals n

Base-3 Representation — Algorithm Steps

Step 1: Convert n to base-3 representation
Step 2: Check each digit
Step 3: Return false if any digit is 2 or greater

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert

Convert n to base-3

Check Digits

Ensure all digits are 0 or 1

Result

Valid if no digit is 2

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool solution(int n) {
    if (n == 0) return true;
    
    // Check base-3 representation
    while (n > 0) {
        if (n % 3 == 2) {  // If any digit is 2, impossible
            return false;
        }
        n /= 3;
    }
    
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Converting to base-3 requires log₃(n) operations

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Base-3 Representation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler