Power of Three

easy math recursion

Problem

Given an integer n, return true if it is a power of three (n = 3^x for some non-negative integer x).

Inputn = 27

Outputtrue

27 = 3³.

def is_power_of_three(n):
    if n < 1: return False
    while n % 3 == 0:
        n //= 3
    return n == 1

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

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}

bool isPowerOfThree(int n) {
    if (n < 1) return false;
    while (n % 3 == 0) n /= 3;
    return n == 1;
}

Explanation

A power of three is a number built only from factors of 3, like 1, 3, 9, 27, 81…. The simplest test is to keep dividing by 3 and see what is left.

If n is less than 1, it cannot be a power of three, so we return false right away. Otherwise, while n is evenly divisible by 3, we divide it: n //= 3. This peels off one factor of 3 at a time.

When the loop stops, n has no more factors of 3. If the number was a true power of three, every factor was a 3 and we are left with exactly 1. If anything else remains, the original number had some other factor mixed in, so it is not a power of three. The answer is simply n == 1.

Example: n = 27 divides to 9, then 3, then 1, and stops at 1, so it returns true. But n = 45 divides to 15, then 5 (no longer divisible by 3), and 5 != 1, so it returns false.

Each division shrinks the number by a factor of 3, so the loop runs about log₃ n times using constant space.

Time: O(log₃ n) Space: O(1)