What is the time complexity of Power of Two?

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

What data structures are used to solve Power of Two?

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

What are the key insights for solving Power of Two?

Insight 1: Powers of two in binary representation have only one bit set to 1. For example, 1 (0001), 2 (0010), 4 (0100), 8 (1000), etc. Insight 2: The bitwise AND operation (`&`) can be used to efficiently check if only one bit is set. `n & (n - 1)` will be 0 if and only if `n` is a power of two.

Which companies ask LeetCode 231. Power of Two in interviews?

This problem is frequently asked at Qualcomm, Snap, Wipro, tcs.

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

Power of Two - LeetCode 231 Solution

Power of Two - Complete Solution Guide

Power of Two is LeetCode problem 231, 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 two. Otherwise, return false . An integer n is a power of two, if there exists an integer x such that n == 2 x . Example 1: Input: n = 1 Output: true Explanation: 2 0 = 1 Example 2: Input: n = 16 Output: true Explanation: 2 4 = 16 Example 3: Input: n = 3 Output: false Constraints: -2 31 <= n <= 2 31 - 1 Follow up: Could you solve it without loops/recursion?

Detailed Explanation

The problem asks whether a given integer `n` is a power of two. This means determining if there exists an integer `x` such that `n = 2<sup>x</sup>`. The input is a single integer `n`, and the output is a boolean value: `true` if `n` is a power of two, and `false` otherwise. The input integer is constrained to be within the range of a 32-bit signed integer.

Solution Approach

The provided solutions leverage the bit manipulation technique. The core idea is that if a number is a power of two, its binary representation will have exactly one bit set to 1. Subtracting 1 from a power of two flips all bits to the right of the single set bit and sets those bits to 1, while the single set bit becomes 0. Performing a bitwise AND between the original number and its predecessor will result in 0 if and only if the original number is a power of two. The solutions also explicitly check if the input number is positive to handle the edge case of negative numbers and zero.

Step-by-Step Algorithm

Step 1: Check if the input `n` is less than or equal to 0. If so, return `false` because powers of two are always positive.
Step 2: Perform the bitwise AND operation: `n & (n - 1)`.
Step 3: Check if the result of Step 2 is equal to 0. If it is, return `true` (it's a power of two); otherwise, return `false`.

Key Insights

Insight 1: Powers of two in binary representation have only one bit set to 1. For example, 1 (0001), 2 (0010), 4 (0100), 8 (1000), etc.
Insight 2: The bitwise AND operation (`&`) can be used to efficiently check if only one bit is set. `n & (n - 1)` will be 0 if and only if `n` is a power of two.
Insight 3: Handling the edge case of negative numbers and zero. Powers of two are always positive.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Math, Bit Manipulation, Recursion.

Companies

Asked at: Qualcomm, Snap, Wipro, tcs.

Power of Two | LeetCode 231

Easy

Math Bit Manipulation Recursion

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

Solution Code

Available in:

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && Integer.bitCount(n) == 1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 231: Power of Two - Detailed explanation and solution approaches.

Topics

Math Bit Manipulation Recursion

Companies

QualcommSnapWiprotcs

Stats

Difficulty:Easy

Languages:4

Companies:4

Problem #:231

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

3 steps

1
Step 1: Check if the input `n` is less than or equal to 0. If so, return `false` because powers of two are always positive.
2
Step 2: Perform the bitwise AND operation: `n & (n - 1)`.
3
Step 3: Check if the result of Step 2 is equal to 0. If it is, return `true` (it's a power of two); 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(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The bitwise AND operation and comparison take constant time regardless of the input size. No extra space is used beyond a few integer variables.

📖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

Iterative Approach

Repeatedly divide `n` by 2 until it becomes 1. If at any point `n` is not divisible by 2, or becomes 0 before reaching 1, it's not a power of two.

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

Trade-offs: Less efficient than the bit manipulation approach. The bit manipulation approach is generally preferred for its constant time complexity.

Using Integer.bitCount() (Java specific)

Java's `Integer.bitCount()` method counts the number of set bits in an integer. If the count is 1, the number is a power of two.

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

Trade-offs: This approach is concise and efficient in Java but relies on a built-in function.

✨

Key Insights

1Insight 1: Powers of two in binary representation have only one bit set to 1. For example, 1 (0001), 2 (0010), 4 (0100), 8 (1000), etc.
2Insight 2: The bitwise AND operation (`&`) can be used to efficiently check if only one bit is set. `n & (n - 1)` will be 0 if and only if `n` is a power of two.
3Insight 3: Handling the edge case of negative numbers and zero. Powers of two are always positive.

📚

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 solution correctly handles this by returning `false` because 0 is not a power of two.
Edge case 2: n = 1. The solution correctly handles this by returning `true` because 2<sup>0</sup> = 1.
Edge case 3: n = -16. Negative numbers are handled correctly as they return `false`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the case of negative numbers or zero. Powers of two are always positive integers.

✗Common mistake 2: Using inefficient approaches like loops without proper termination conditions or relying on floating-point calculations, which can introduce precision errors.

✅

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: Checking for valid memory allocations in systems programming. Memory is often allocated in powers of two (e.g., 2KB, 4KB, etc.).

🏦Real-world scenario 2: Data structures and algorithms. Some algorithms utilize properties of powers of two (e.g., binary trees, hash tables).

💡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

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ 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: July 22, 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

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

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

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 bit manipulation techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?