LeetCode 326 Power of Three - Step by Step Breakdown(Easy, Java, O(n))

LeetCode 326. Power of Three

This code determines whether a given integer n is a power of three. A power of three is any integer that can be expressed as (3^k) where (k) is a non-negative integer (e.g., (3^0 = 1), (3^1 = 3), (3^2 = 9), etc.).

---

Step-by-Step Breakdown

1. Edge Case Handling

if (n <= 0) {
    return false;
}

• Purpose: Immediately return false if n is non-positive.
• Reasoning:
  • Powers of three are always positive ((3^k > 0) for any (k \geq 0)).
  • If n is zero or negative, it cannot be a power of three.

2. Division Loop

while (n % 3 == 0) {
    n /= 3;
}

• Purpose: Repeatedly divide n by 3 as long as it is divisible by 3.
• How it Works:
  • Condition: n % 3 == 0 checks if n is divisible by 3.
  • Operation: If divisible, divide n by 3 (n /= 3).
  • Termination: The loop stops when n is no longer divisible by 3.
• Example:
  • For n = 27:
    • (27 \div 3 = 9) (first iteration).
    • (9 \div 3 = 3) (second iteration).
    • (3 \div 3 = 1) (third iteration).
    • Loop ends because (1 \% 3 \neq 0).

3. Final Check

return n == 1;

• Purpose: Determine if the reduced n is 1.
• Logic:
  • If n is a power of three, repeated division by 3 will eventually reduce it to 1.
  • If n is not a power of three, the loop will terminate with n != 1.
• Examples:
  • Power of Three: n = 9 reduces to 1 → returns true.
  • Not a Power of Three: n = 45 reduces to 5 → returns false.

---

Why This Approach Works

1. Mathematical Insight:

   • Any power of three can be broken down into a product of 3s. For example:
     • (81 = 3 \times 3 \times 3 \times 3).
   • Repeated division by 3 will eventually yield 1 if n is a power of three.

2. Termination Guarantee:

   • The loop ensures n is reduced as much as possible.
   • The final check (n == 1) confirms whether the reduction was complete.

3. Efficiency:

   • Time Complexity: (O(\log_3 n)) because each iteration reduces n by a factor of 3.
   • Space Complexity: (O(1)) (no extra space is used).

---

Test Cases

---

Full Solution

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

Alternative Approaches (for Context)

1. Logarithmic Method:

   • Compute (\log_3(n)) and check if it is an integer.
   • Issue: Precision errors with floating-point arithmetic.

2. Integer Limitation:

   • The largest power of 3 in 32-bit integers is (3^{19} = 1162261467).
   • Check if (1162261467 \% n == 0).
   • Advantage: Constant time ((O(1))).

3. Recursion:

   • Recursively divide n by 3 until n == 1 or n % 3 != 0.
   • Disadvantage: Less efficient due to function call overhead.

---

Key Takeaways

• The given solution is efficient and easy to understand.
• It leverages division and modulo operations to systematically reduce n.
• Edge cases (n <= 0) are handled upfront for correctness.

This approach is optimal for the problem constraints and demonstrates a clear application of loop-based reduction in number theory problems.