2025-03-04 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 4

Description

Check if Number is a Sum of Powers of Three

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 == 3x.

 

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 31 + 32

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 30 + 32 + 34

Example 3:

Input: n = 21
Output: false

 

Constraints:

  • 1 <= n <= 107

Solution

class Solution {
  vector<int> powers{4782969, 1594323, 531441, 177147, 59049, 19683, 6561, 2187, 729, 243, 81, 27, 9, 3, 1};
public:
  bool checkPowersOfThree(int n) {
    for(auto power : powers) {
      if(n >= power) n -= power;
    }
    return n == 0;
  }
};

// Accepted
// 129/129 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 41.55 % of cpp submissions (7.9 MB)
Algorithm