1780. Check if Number is a Sum of Powers of Three

UnknownView on LeetCode

Math

Time: O(log n)

Space: O(1)

Intuition

Check if n can be represented as sum of distinct powers of 3. Greedily try to subtract highest powers of 3.

Algorithm

1While n > 0: if n % 3 == 0, divide by 3. If n % 3 == 1, subtract 1 and divide by 3. If n % 3 == 2, return false (can't use power twice).

Common Pitfalls

•In base 3, each digit must be 0 or 1 (distinct powers). If any digit is 2, return false.

1780.cs

// Approach: Repeatedly divide by 3; if any remainder is 2 return false (base-3 representation can only use 0/1).
// Time: O(log n) Space: O(1)

public class Solution
{
    public bool CheckPowersOfThree(int n)
    {
        while (n > 1)
        {
            int r = n % 3;
            if (r == 2)
                return false;
            n /= 3;
        }

        return true;
    }
}

Was this solution helpful?