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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Number is a Sum of Powers of Three

Number: 1889

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given an integer n, determine if it is possible to express n as the sum of distinct powers of three. In other words, check whether n can be represented as the sum of different terms from the series 3^0, 3^1, 3^2, ..., where each power is used at most once.

Key Insights

  • A number can be represented as a sum of distinct powers of three if its base-3 representation contains only 0s and 1s (i.e., it does not contain the digit 2).
  • Converting the integer to a base-3 string and verifying the absence of '2' is an efficient method.
  • Alternatively, one can subtract the largest possible power of three iteratively until either reaching zero or finding the representation to be impossible.
  • This approach directly leverages the unique properties of numeral systems and subset sum problems.

Space and Time Complexity

Time Complexity: O(log_3(n)) for converting n to base-3. Space Complexity: O(log_3(n)) for storing the base-3 representation.

Solution

The solution involves converting the given integer n into its base-3 representation. If this representation contains the digit '2', it indicates that a power of three would need to be used more than once to form the sum, which is not allowed. Therefore, if '2' is found, the function returns false; otherwise, it returns true.

Data Structures and Approaches:

  • Use a string to hold the base-3 representation.
  • Use string scanning to check for the forbidden digit '2'.
  • This method efficiently leverages the properties of number bases to solve the problem with minimal computations.

Code Solutions

# Convert the integer n to its base-3 representation and check for '2'
def checkPowersOfThree(n: int) -> bool:
    # Convert n to a base-3 string
    base3 = ""
    while n:
        # Get the remainder when n is divided by 3, which is a digit in base-3
        base3 = str(n % 3) + base3
        n //= 3
    # If '2' is present in the base-3 representation, it's not possible to form n
    return '2' not in base3

# Example execution
print(checkPowersOfThree(12))  # Expected output: True, since 12 = 3^1 + 3^2
print(checkPowersOfThree(91))  # Expected output: True, since 91 = 3^0 + 3^2 + 3^4
print(checkPowersOfThree(21))  # Expected output: False
← Back to All Questions