algoadvance

Leetcode 326. Power of Three

Problem Statement

Given an integer n, write a function to determine if it is a power of three. An integer n is a power of three if there exists an integer x such that n == 3^x.

Clarifying Questions

  1. What is the range of the input integer n?
    • Assume: n can be any 32-bit signed integer, which means it can range from -2^31 to 2^31 - 1.
  2. Can the input n be negative or zero?
    • Yes, the input can be negative or zero.
  3. What should be returned for negative numbers and zero?
    • Any non-positive number should return false, as powers of three are positive numbers.
  4. Is there any constraint on time complexity?
    • Preferably, the solution should be efficient enough to handle the range mentioned (i.e., -2^31 to 2^31 - 1).

Strategy

  1. Initial Check: If n is less than or equal to zero, return false immediately, since powers of three are always positive.

  2. Iterative Solution: Iterate to divide n by 3 continuously:
    • While n is greater than 1, check if n is divisible by 3.
    • If it isn’t, return false because n cannot be a power of three.
    • Divide n by 3 and continue the loop.
    • If the loop completes and n is reduced to 1, return true.
  3. Alternative Approach (Mathematical): Use logarithms to determine if n is a power of three:
    • If n is positive, compute log(n) / log(3). If the result is an integer, then n is a power of three.

Code

Here is the C++ implementation of the iterative approach:

#include <iostream>
using namespace std;

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

int main() {
    int test1 = 27;   // Expected: true (3^3)
    int test2 = 0;    // Expected: false
    int test3 = 9;    // Expected: true (3^2)
    int test4 = 45;   // Expected: false

    cout << std::boolalpha;
    cout << "Is " << test1 << " a power of three? " << isPowerOfThree(test1) << endl;
    cout << "Is " << test2 << " a power of three? " << isPowerOfThree(test2) << endl;
    cout << "Is " << test3 << " a power of three? " << isPowerOfThree(test3) << endl;
    cout << "Is " << test4 << " a power of three? " << isPowerOfThree(test4) << endl;

    return 0;
}

Time Complexity

This method ensures that we efficiently determine whether n is a power of three, taking into account all edge cases, including negative numbers and zero.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI