[Leetcode][1780. Check if Number is a Sum of Powers of Three] 3 Solutions: Tricky, Recursive and Base 3 convertion

By Long Luo

This article is the solution of Problem 1780. Check if Number is a Sum of Powers of Three.

Brute Froce

This method is tricky.

We can easy get a table that recorded all the numbers using Math.power(3, n) between $1$ to $10^7$.

Then scanning from the largest to the smallest, if find a value smaller or equal to $n$, then subtract it from $n$.

Repeat it until to $0$.

public static boolean checkPowersOfThree(int n) {
    int[] nums = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969};
    int idx = nums.length - 1;
    while (idx >= 0 && n > 0) {
        while (idx >= 0 && nums[idx] > n) {
            idx--;
        }

        if (nums[idx] == n) {
            return true;
        }

        n -= nums[idx];
        idx--;
    }

    return false;
}

Analysis

• Time Complexity: $O(1)$
• Space Complexity: $O(1)$

Base 3 Conversion

As the sum of distinct powers of 3, which means if we convert n to a base 3, every certain position can only be 0 or 1.

public static boolean checkPowersOfThree_base3(int n) {
    while (n > 0) {
        if (n % 3 == 2) {
            return false;
        }
        n /= 3;
    }

    return true;
}

Analysis

• Time Complexity: $O(logn)$
• Space Complexity: $O(1)$

Recursive

We can make our code more clean. Just One Line Is Enough!

public static boolean checkPowersOfThree_rec(int n) {
    return n < 2 || (n % 3 != 2 && checkPowersOfThree_rec(n / 3));
}

Analysis

• Time Complexity: $O(logn)$
• Space Complexity: $O(1)$

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗