Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1780.html

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

Level

Medium

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.

An integer y is a power of three if there exists an integer x such that y == 3^x.

Example 1:

Input: n = 12

Output: true

Explanation: 12 = 3^1 + 3^2

Example 2:

Input: n = 91

Output: true

Explanation: 91 = 3^0 + 3^2 + 3^4

Example 3:

Input: n = 21

Output: false

Constraints:

  • 1 <= n <= 10^7

Solution

The integer n can always be converted into a base three representation. Each digit in base three representation is 0, 1 or 2. To represent n as the sum of distinct powers of three, each digit in base three representation must be 0 or 1.

In this problem, we do not actually convert n into a base three representation. We only need to calculate the digits and we do not care the order of the digits. Therefore, while n > 0, calculate the n % 3 each time and if a remainder 2 is found, return false. Otherwise, let n = n / 3 and repeat the process until n becomes 0. If n becomes 0 without any remainder 2 met, return true.

  • class Solution {
        public boolean checkPowersOfThree(int n) {
            while (n > 0) {
                int remainder = n % 3;
                if (remainder == 2)
                    return false;
                n /= 3;
            }
            return true;
        }
    }
    
    ############
    
    class Solution {
        public boolean checkPowersOfThree(int n) {
            while (n > 0) {
                if (n % 3 > 1) {
                    return false;
                }
                n /= 3;
            }
            return true;
        }
    }
    
  • // OJ: https://leetcode.com/problems/check-if-number-is-a-sum-of-powers-of-three/
    // Time: O(log_3^N)
    // Space: O(1)
    class Solution {
    public:
        bool checkPowersOfThree(int n) {
            while (n % 3 == 0 || (n % 3 == 1 && n != 1)) {
                if (n % 3 == 1) n -= 1;
                n /= 3;
            }
            return n == 1;
        }
    };
    
  • class Solution:
        def checkPowersOfThree(self, n: int) -> bool:
            while n:
                if n % 3 > 1:
                    return False
                n //= 3
            return True
    
    ############
    
    # 1780. Check if Number is a Sum of Powers of Three
    # https://leetcode.com/problems/check-if-number-is-a-sum-of-powers-of-three/
    
    class Solution:
        def checkPowersOfThree(self, n: int) -> bool:
            while n > 1:
                if n % 3 == 2: return False
                
                n //= 3
                
            return n == 1
    
    
  • func checkPowersOfThree(n int) bool {
    	for n > 0 {
    		if n%3 > 1 {
    			return false
    		}
    		n /= 3
    	}
    	return true
    }
    
  • function checkPowersOfThree(n: number): boolean {
        while (n) {
            if (n % 3 > 1) return false;
            n = Math.floor(n / 3);
        }
        return true;
    }
    
    

All Problems

All Solutions