algoadvance

Leetcode 326. Power of Three

Problem Statement

Determine if an integer ( n ) is a power of three. More specifically, check if there exists an integer ( x ) such that ( 3^x = n ).

Example 1:

• Input: ( n = 27 )
• Output: True
• Explanation: ( 27 ) is ( 3^3 ).

Example 2:

• Input: ( n = 0 )
• Output: False
• Explanation: ( 0 ) is not a power of three.

Example 3:

• Input: ( n = 9 )
• Output: True
• Explanation: ( 9 ) is ( 3^2 ).

Example 4:

• Input: ( n = 45 )
• Output: False
• Explanation: ( 45 ) is not a power of three.

Clarifying Questions

1. What are the constraints on the value of ( n )?
   • The value of ( n ) can be as large as ( 2^{31} - 1 ) (i.e., the maximum value of a signed 32-bit integer).
2. Can ( n ) be negative?
   • Yes, ( n ) can be negative. Negative numbers cannot be powers of three as ( 3^x ) where ( x ) is an integer is always positive.

Strategy

To determine if ( n ) is a power of three, we can follow these strategies:

1. Iterative Approach:
   • Continuously divide ( n ) by 3. If ( n ) becomes 1 after repeated divisions by 3, it is a power of three. If at any step ( n ) is not divisible by 3 and isn’t 1, then it is not a power of three.
2. Mathematical Approach:
   • Calculate the largest power of 3 within the 32-bit integer range, which is ( 3^{19} ) (since ( 3^{20} > 2^{31} - 1 )). If ( n ) is a power of three, it must be a divisor of ( 3^{19} ).

We will implement the first method because it is more straightforward and easier to understand.

Code

Here’s a solution using the iterative approach:

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

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPowerOfThree(27)); // true
        System.out.println(solution.isPowerOfThree(0));  // false
        System.out.println(solution.isPowerOfThree(9));  // true
        System.out.println(solution.isPowerOfThree(45)); // false
    }
}

Time Complexity

• Time Complexity: ( O(\log_3 n) ). In the worst case, we keep dividing ( n ) by 3 until it becomes 1, which takes ( \log_3 n ) divisions.

• Space Complexity: ( O(1) ). We only use a couple of variables for keeping track of ( n ) and the loop, so the space requirement is constant.

Feel free to ask any further questions or for additional clarifications!

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?