Skip to content

326. Power of Three

Description

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

 

Example 1:

Input: n = 27
Output: true
Explanation: 27 = 33

Example 2:

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

Example 3:

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

 

Constraints:

  • -231 <= n <= 231 - 1

 

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

Solutions

Solution 1: Trial Division

Thinking

Decide whether \(n\) is a power of three. Repeated multiplication works, but trial division is direct: while \(n>2\), reject a non-multiple of \(3\), otherwise divide by \(3\). The last residue must be \(1\).

If \(n \gt 2\), we can continuously divide \(n\) by \(3\). If it's not divisible, it means \(n\) is not a power of \(3\), otherwise we continue dividing by \(3\) until \(n\) is less than or equal to \(2\). If \(n\) equals \(1\), it means \(n\) is a power of \(3\), otherwise it's not a power of \(3\).

Time complexity \(O(\log_3n)\), space complexity \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n > 2:
            if n % 3:
                return False
            n //= 3
        return n == 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public boolean isPowerOfThree(int n) {
        while (n > 2) {
            if (n % 3 != 0) {
                return false;
            }
            n /= 3;
        }
        return n == 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n > 2) {
            if (n % 3) {
                return false;
            }
            n /= 3;
        }
        return n == 1;
    }
};

1
2
3
4
5
6
7
8
9
func isPowerOfThree(n int) bool {
    for n > 2 {
        if n%3 != 0 {
            return false
        }
        n /= 3
    }
    return n == 1
}

1
2
3
4
5
6
7
8
9
function isPowerOfThree(n: number): boolean {
    while (n > 2) {
        if (n % 3 !== 0) {
            return false;
        }
        n = Math.floor(n / 3);
    }
    return n === 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn is_power_of_three(mut n: i32) -> bool {
        while n > 2 {
            if n % 3 != 0 {
                return false;
            }
            n /= 3;
        }
        n == 1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
    while (n > 2) {
        if (n % 3 !== 0) {
            return false;
        }
        n = Math.floor(n / 3);
    }
    return n === 1;
};

Solution 2: Mathematics

Thinking

Trial division takes \(O(\log n)\) steps. The largest power of three in \(32\) bits is \(3^{19}=1162261467\); a positive \(n\) is a power of three iff it divides that constant. One modulo suffices.

If \(n\) is a power of \(3\), then the maximum value of \(n\) is \(3^{19} = 1162261467\). Therefore, we only need to check if \(n\) is a divisor of \(3^{19}\).

Time complexity \(O(1)\), space complexity \(O(1)\).

1
2
3
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

1
2
3
4
5
class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

1
2
3
func isPowerOfThree(n int) bool {
    return n > 0 && 1162261467%n == 0
}

1
2
3
function isPowerOfThree(n: number): boolean {
    return n > 0 && 1162261467 % n == 0;
}

1
2
3
4
5
impl Solution {
    pub fn is_power_of_three(mut n: i32) -> bool {
        n > 0 && 1162261467 % n == 0
    }
}

1
2
3
4
5
6
7
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
    return n > 0 && 1162261467 % n == 0;
};

Comments