Power of Three - LeetCode 326 - DSA and Algorithm - JavaScript

 

The Power of three algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.

The question for an algorithm is,

Given a positive integer, write a function to find if it is a power of three or not.

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³

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).

Let's start with the algorithm,

var  isPowerThree = function(n) {

  // 1 (3^0) is the smallest power of three.

  if (n < 1) {

    return false;

  }

  // Let's find out if we can divide the number by three

  // many times without remainder.

  while (n !== 1) {

    if (n % 3 !== 0) {

      // For every case when remainder isn't zero we can say that this number

      // couldn't be a result of power of three.

      return false;

    }

    n /= 3;

  }

  return true;

}; 

Here, we just keep dividing the number by three unless the number becomes 1 and every time we do so, we check that remainder after division is always 0. Otherwise, the number can't be a power of three.

I hope you understood the algorithm. If you have any doubts, please let us know in the comments.