Problem

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.

Examples

Example 1:

1
2

Input: n = 27
Output: true

Example 2:

1
2

Input: n = 0
Output: false

Example 3:

1
2

Input: n = 9
Output: true

Solution

Method 1 - Naive Division by 3

Intuition

Keep dividing the number by 3. If at any step the remainder is not zero, it’s not a power of three. If we reach 1, it is a power of three.

Approach

  1. If n is less than 1, return false.
  2. While n is divisible by 3, divide n by 3.
  3. If n becomes 1, return true; otherwise, return false.

Code

1
2
3
4
5
6
7
8

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

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

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

class Solution {
	fun isPowerOfThree(n: Int): Boolean {
		if (n < 1) return false
		var x = n
		while (x % 3 == 0) x /= 3
		return x == 1
	}
}
1
2
3
4
5
6
7

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

impl Solution {
	pub fn is_power_of_three(n: i32) -> bool {
		if n < 1 { return false; }
		let mut x = n;
		while x % 3 == 0 { x /= 3; }
		x == 1
	}
}
1
2
3
4
5

function isPowerOfThree(n: number): boolean {
	if (n < 1) return false;
	while (n % 3 === 0) n /= 3;
	return n === 1;
}

Complexity

  • ⏰ Time complexity: O(log n), because each division by 3 reduces n by a factor of 3.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used.

Method 2 - Division by 9

Intuition

If a number is a power of 3, it is also a power of 9 (since 9 = 3^2). We can keep dividing by 9 and check if the result is 1 or 3.

Approach

  1. If n is 0, return false.
  2. While n is divisible by 9, divide n by 9.
  3. If n is 1 or 3, return true; otherwise, return false.

Code

1
2
3
4
5
6
7
8

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

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

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

class Solution {
	fun isPowerOfThree(n: Int): Boolean {
		if (n == 0) return false
		var x = n
		while (x % 9 == 0) x /= 9
		return x == 1 || x == 3
	}
}
1
2
3
4
5
6
7

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

impl Solution {
	pub fn is_power_of_three(n: i32) -> bool {
		if n == 0 { return false; }
		let mut x = n;
		while x % 9 == 0 { x /= 9; }
		x == 1 || x == 3
	}
}
1
2
3
4
5

function isPowerOfThree(n: number): boolean {
	if (n === 0) return false;
	while (n % 9 === 0) n /= 9;
	return n === 1 || n === 3;
}

Complexity

  • ⏰ Time complexity: O(log n), because each division by 9 reduces n by a factor of 9.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used.

Method 3 - Using Logarithm

Intuition

If n is a power of three, then log base 3 of n should be an integer. We can use logarithms to check this.

Approach

  1. If n is less than 1, return false.
  2. Compute log base 3 of n using change of base: log(n) / log(3).
  3. If the result is an integer (i.e., modulo 1 is zero), return true; otherwise, return false.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
	bool isPowerOfThree(int n) {
		if (n < 1) return false;
		double log3 = log10(n) / log10(3);
		return fmod(log3, 1) == 0;
	}
};
1
2
3
4
5
6
7
8

import "math"
func isPowerOfThree(n int) bool {
	if n < 1 {
		return false
	}
	log3 := math.Log10(float64(n)) / math.Log10(3)
	return math.Mod(log3, 1) == 0
}
1
2
3
4
5
6
7

class Solution {
	public boolean isPowerOfThree(int n) {
		if (n < 1) return false;
		double log3 = Math.log10(n) / Math.log10(3);
		return log3 % 1 == 0;
	}
}
1
2
3
4
5
6
7

class Solution {
	fun isPowerOfThree(n: Int): Boolean {
		if (n < 1) return false
		val log3 = Math.log10(n.toDouble()) / Math.log10(3.0)
		return log3 % 1 == 0.0
	}
}
1
2
3
4
5
6
7

import math
class Solution:
	def isPowerOfThree(self, n: int) -> bool:
		if n < 1:
			return False
		log3 = math.log10(n) / math.log10(3)
		return log3 % 1 == 0
1
2
3
4
5
6
7

impl Solution {
	pub fn is_power_of_three(n: i32) -> bool {
		if n < 1 { return false; }
		let log3 = (n as f64).log10() / 3f64.log10();
		log3 % 1.0 == 0.0
	}
}
1
2
3
4
5

function isPowerOfThree(n: number): boolean {
	if (n < 1) return false;
	const log3 = Math.log10(n) / Math.log10(3);
	return log3 % 1 === 0;
}

Complexity

  • ⏰ Time complexity: O(1), since logarithm and division are constant time operations.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used.

Method 4 - Using Max 3^x Less Than Integer Max Value

Intuition

The largest power of 3 that fits in a 32-bit signed integer is 3^19 = 1162261467. If n is a power of 3, it must divide 3^19 with no remainder.

Approach

  1. If n is less than or equal to 0, return false.
  2. Check if 1162261467 % n == 0. If true, n is a power of 3.

Code

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
4
5

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

class Solution {
	fun isPowerOfThree(n: Int): Boolean {
		return n > 0 && 1162261467 % n == 0
	}
}
1
2
3

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

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

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

Complexity

  • ⏰ Time complexity: O(1), since it is a single arithmetic check.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used.