What is the time complexity of Power of Three?

The optimal solution has a time complexity of O(log n).

What data structures are used to solve Power of Three?

This problem uses Math, Recursion. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Power of Three?

Insight 1: Repeatedly dividing by 3: If a number is a power of three, repeatedly dividing it by 3 will eventually result in 1. If at any point the remainder is not 0, it's not a power of three. Insight 2: Handling negative numbers and zero: Powers of three are always positive integers. Negative numbers and zero cannot be powers of three.

Which companies ask LeetCode 326. Power of Three in interviews?

This problem is frequently asked at Goldman Sachs.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Power of Three - LeetCode 326 Solution

Q: How to solve Power of Three?

The provided solution uses an iterative approach. It first checks if the input `n` is less than or equal to 0. If it is, it immediately returns `false` because powers of three are always positive. Otherwise, it enters a `while` loop that continues as long as `n` is divisible by 3. Inside the loop, `n` is repeatedly divided by 3 using integer division. Finally, the function checks if `n` is equal to 1. If it is, it means that the original number was a power of three; otherwise, it wasn't.

Power of Three - Complete Solution Guide

Power of Three is LeetCode problem 326, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an integer n , return true if it is a power of three. Otherwise, return false . 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 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). Constraints: -2 31 <= n <= 2 31 - 1 Follow up: Could you solve it without loops/recursion?

Detailed Explanation

The problem asks to determine if a given integer `n` is a power of three. This means checking if there exists an integer `x` such that 3 raised to the power of `x` equals `n`. The input is an integer `n`, and the output is a boolean value: `true` if `n` is a power of three, and `false` otherwise. The input integer is constrained to be within the range of a 32-bit integer.

Solution Approach

The provided solution uses an iterative approach. It first checks if the input `n` is less than or equal to 0. If it is, it immediately returns `false` because powers of three are always positive. Otherwise, it enters a `while` loop that continues as long as `n` is divisible by 3. Inside the loop, `n` is repeatedly divided by 3 using integer division. Finally, the function checks if `n` is equal to 1. If it is, it means that the original number was a power of three; otherwise, it wasn't.

Step-by-Step Algorithm

Step 1: Check if `n` is less than or equal to 0. If true, return `false`.
Step 2: Enter a `while` loop that continues as long as `n` is divisible by 3 ( `n % 3 == 0`).
Step 3: Inside the loop, divide `n` by 3 using integer division (`n //= 3` or `n /= 3`).
Step 4: After the loop, check if `n` is equal to 1. If true, return `true`; otherwise, return `false`.

Key Insights

Insight 1: Repeatedly dividing by 3: If a number is a power of three, repeatedly dividing it by 3 will eventually result in 1. If at any point the remainder is not 0, it's not a power of three.
Insight 2: Handling negative numbers and zero: Powers of three are always positive integers. Negative numbers and zero cannot be powers of three.
Insight 3: Efficient modulo and division operations: Using modulo (%) and integer division (// or /) operations is efficient for repeatedly checking divisibility by 3.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(1)

Topics

This problem involves: Math, Recursion.

Companies

Asked at: Goldman Sachs.

Power of Three | LeetCode 326

Easy

Math Recursion

Time: O(log n)Space: O(1)

Solution Code

Available in:

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

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 326: Power of Three - Detailed explanation and solution approaches.

Topics

Math Recursion

Companies

Goldman Sachs

Stats

Difficulty:Easy

Languages:4

Companies:1

Problem #:326

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Check if `n` is less than or equal to 0. If true, return `false`.
2
Step 2: Enter a `while` loop that continues as long as `n` is divisible by 3 ( `n % 3 == 0`).
3
Step 3: Inside the loop, divide `n` by 3 using integer division (`n //= 3` or `n /= 3`).
4
Step 4: After the loop, check if `n` is equal to 1. If true, return `true`; otherwise, return `false`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is logarithmic because the number of times the `while` loop iterates is proportional to the logarithm base 3 of `n`. Each iteration reduces `n` by a factor of 3. The space complexity is constant because only a few variables are used, regardless of the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using Math.log

Calculate log₃(n) using the change of base formula: log₃(n) = log₁₀(n) / log₁₀(3). If the result is an integer, then n is a power of 3.

Time: O(1)Space: O(1)

Trade-offs: This approach is faster than the iterative one but might introduce slight inaccuracies due to floating-point arithmetic. The iterative approach is more precise.

Pre-calculated powers of 3

Pre-calculate powers of 3 up to the maximum possible value within the given constraint and check if n is present in the list.

Time: O(1)Space: O(log₃(MAX_INT))

Trade-offs: This approach offers O(1) lookup time after the pre-calculation, but requires extra space to store the pre-calculated powers. Suitable if you are checking for multiple numbers.

✨

Key Insights

1Insight 1: Repeatedly dividing by 3: If a number is a power of three, repeatedly dividing it by 3 will eventually result in 1. If at any point the remainder is not 0, it's not a power of three.
2Insight 2: Handling negative numbers and zero: Powers of three are always positive integers. Negative numbers and zero cannot be powers of three.
3Insight 3: Efficient modulo and division operations: Using modulo (%) and integer division (// or /) operations is efficient for repeatedly checking divisibility by 3.

📚

Key Terms Explained

For Students

Recursion

A function that calls itself to solve smaller versions of the same problem.

Edge Cases

Edge case 1: n = 0: The code correctly handles this by returning `false` in the initial check.
Edge case 2: n = 1: The code correctly identifies 1 as a power of three (3⁰ = 1).
Edge case 3: n = Negative numbers: The code correctly handles negative inputs by returning `false`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the base case of n <= 0. This will lead to incorrect results for non-positive inputs.

✗Common mistake 2: Using floating-point arithmetic for division without considering potential rounding errors. Integer division is crucial for accuracy.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: In data structures and algorithms, checking if a number is a power of three could be useful in specific tree-like structures where nodes are organized based on powers of three.

🏦Real-world scenario 2: In game development or simulations, this could be used for efficient resource management where resources are arranged in a grid based on powers of three.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 25, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Power of Three"?

For this easy-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether recursion techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?