Power of Three.md

Solution 1 - Using Loop

Algorithm

If a number is a power of 3, we can keep dividing it by 3 until we end up with a value of 1.

Code

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

Notes

This algorithm works for any "Power of X" question for X = 2, 3, 4,...

Time/Space Complexity

• Time Complexity
• if number of bits in int n is capped at 32: O(1)
• if number of bits is allowed to grow: O(log n)
• Space Complexity: O(1)

Solution 2 - Base Conversion

Algorithm

1. Convert the number to base-3 representation.
2. Check if it starts with 10

Code

class Solution {
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("10*");
    }
}

Notes

This algorithm works for any "Power of X" question for X = 2, 3, 4,...

Time/Space Complexity

• Time Complexity
  • if number of bits in int n is capped at 32: O(1)
  • if number of bits is allowed to grow: O(log n) since base conversion is implemented as repeated division
• Space Complexity: O(1)

Solution 3 - Integer Limitations

Algorithm

This algorithm only works since 3 is a prime number.

1. 3¹⁹ = 1162261467 is the biggest power of 3 less than Integer.MAX_VALUE.
2. Since 3 is a prime number, the only divisors of 3¹⁹ are 3⁰, 3¹, 3², ... 3¹⁹, which happen to all be powers of 3.
3. Return true if n is positive and 1162261467 is divisible by n

Code

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 &&
               1162261467 % n == 0;
    }
}

Time/Space Complexity

• Time Complexity
  • if number of bits in int n is capped at 32: O(1)
  • if number of bits is allowed to grow: O(log n) due to the % operator
• Space Complexity: O(1)

Links

• github.com/RodneyShag