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: true

💡 Note: 91 can be represented as 81 + 9 + 1 = 3⁴ + 3² + 3⁰, which are distinct powers of three

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

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

✓ Base-3 Representation

⏱️ Time: O(log n) Space: O(1)

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 (no digit 2). This is because digit 2 would mean using the same power of 3 twice.

Brute Force - Generate All Subsets

⏱️ Time: O(2^k) Space: O(k)

Generate powers of three up to n, then check all possible subsets to see if any combination sums to n. This explores every possible way to combine distinct powers of three.

Greedy Approach

⏱️ Time: O(log n) Space: O(1)

Start with the largest power of 3 that doesn't exceed n, subtract it, and repeat. If we can reduce n to exactly 0, then it's possible. This works because powers of 3 have a special property.

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;
    
    while (n > 0) {
        // Find largest power of 3 <= n
        int power = 1;
        while (power * 3 <= n) {
            power *= 3;
        }
        
        // Subtract this power from n
        n -= power;
        
        // If we've seen this power before in the same number,
        // we need to check if remaining n can be expressed
        // without using powers >= current power
        if (n > 0) {
            // Check if remaining n has any digit >= 2 in base 3
            int temp = n;
            while (temp > 0) {
                if (temp % 3 >= 2) {
                    return false;
                }
                temp /= 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Base-3 Representation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler