We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if Number is a Sum of Powers of Three

Difficulty: Medium

Problem Description

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

Key Insights

  • A number can be expressed as the sum of distinct powers of three if it can be represented in base 3 without using the digit 2.
  • The powers of three are 1, 3, 9, 27, 81, etc.
  • The problem can be solved by continuously dividing the number by 3 and checking the remainders.
  • If we encounter a remainder of 2 during the division, then it's impossible to express the number in the required form.

Space and Time Complexity

Time Complexity: O(log n) - because we continuously divide n by 3. Space Complexity: O(1) - we use a constant amount of space.

Solution

To determine whether a number can be expressed as a sum of distinct powers of three, we can convert the number to base 3 and check for the presence of the digit '2'. If '2' is present, it means that the number cannot be represented as required. The algorithm will repeatedly divide the number by 3, checking the remainder at each step.

Code Solutions

def checkPowersOfThree(n: int) -> bool:
    while n > 0:
        if n % 3 == 2:  # If the remainder is 2, return False
            return False
        n //= 3  # Divide n by 3
    return True  # If we finish the loop, return True
← Back to All Questions