Follow

Follow
326. Power of Three

326. Power of Three

How to identify if an integer is a power of three

Nhut Nguyen's photo
Nhut Nguyen
·Dec 19, 2022·

2 min read

Problem statement

Given an integer n, return true if it is a power of three. Otherwise, return false.

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

Example 1

Input: n = 27
Output: true
Explanation: 27 = 3^3.

Example 2

Input: n = 0
Output: false
Explanation: There is no x where 3^x = 0.

Example 3

Input: n = -1
Output: false
Explanation: There is no x where 3^x = (-1).

Constraints

  • -2^31 <= n <= 2^31 - 1.

Follow up: Could you solve it without loops/recursion?

Solution 1: Recursion

Code

#include <iostream>
using namespace std;
bool isPowerOfThree(int n) {
    while (n % 3 == 0 && n > 0) {
        n /= 3;
    }
    return n == 1;

}
int main() {
    cout << isPowerOfThree(27) << endl;
    cout << isPowerOfThree(0) << endl;
    cout << isPowerOfThree(-1) << endl;
}
Output:
1
0
0

Complexity

  • Runtime: O(logn).

  • Extra space: O(1).

Solution 2: Mathematics and the constraints of the problem

A power of three must divide another bigger one, i.e. 3^x | 3^y where 0 <= x <= y.

Because the constraint of the problem is n <= 2^31 - 1, you can choose the biggest power of three in this range to test the others.

It is 3^19 = 1162261467. The next power will exceed 2^31 = 2147483648.

Code

#include <iostream>
using namespace std;
bool isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}
int main() {
    cout << isPowerOfThree(27) << endl;
    cout << isPowerOfThree(0) << endl;
    cout << isPowerOfThree(-1) << endl;
}
Output:
1
0
0

Complexity

  • Runtime: O(1).

  • Extra space: O(1).

References

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.

Did you find this article valuable?

Support LeetSolve by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this