Power of Two

easyFREEMath & Bit ManipulationDSA for AI Engineers

Given an integer n, return True if it is a power of two.

Example

Input

Output

True

Reasoning

Input: n is a single integer, here 16. It can be any 32-bit signed value, so zero and negative numbers are valid inputs too.
The math: n is a power of two when $n = 2^k$ for some whole number $k \ge 0$ . For the sample, $16 = 2 \times 2 \times 2 \times 2 = 2^4$ , so $k = 4$ and the answer is True.
Contrast: $12 = 2^2 \times 3$ is not, because its factorisation contains an odd factor other than $1$ . Likewise $3$ sits between $2^1 = 2$ and $2^2 = 4$ , which gives False.
Edges to notice: $1 = 2^0$ counts, so 1 gives True. Every $2^k$ is strictly positive, so $0$ and all negative inputs (even $-16$ ) give False.
Output: a single boolean, True for the sample. Notice that the powers of two thin out fast: there are only 31 of them in the whole input range, from $2^0$ up to $2^{30}$ .

Constraints

-2^31 <= n <= 2^31 - 1

More from DSA for AI Engineers

Single Numbereasy Binary Tree Level Order Traversaleasy Flatten Binary Tree to Linked Listmedium Serialize and Deserialize Binary Treehard Coin Changemedium

Concept primer

Background Knowledge

The problem "Power of Two" involves determining whether a given integer n is a power of two. To understand this, it's essential to know what it means for a number to be a power of two. A power of two is any number that can be expressed as $2^x$ , where $x$ is an integer. For example, 1, 2, 4, 8, and 16 are all powers of two because they can be expressed as $2^0$ , $2^1$ , $2^2$ , $2^3$ , and $2^4$ , respectively.

In the context of bit manipulation, which is a crucial aspect of this problem, it's important to understand how numbers are represented in binary. In binary, each digit (or bit) represents a power of two. For instance, the number 8 in binary is 1000, where the leftmost bit represents $2^3$ , and the other bits represent lower powers of two. This binary representation is key to solving the "Power of Two" problem efficiently.

Understanding the properties of powers of two and how they are represented in binary will help in devising an efficient algorithm. Specifically, recognizing that powers of two have exactly one bit set to 1 in their binary representation (e.g., 8 is 1000, 16 is 10000) can guide the development of a solution that leverages bitwise operations.

Algorithm/Approach

The general approach to solving this type of problem involves using bit manipulation techniques. Bit manipulation allows for direct manipulation of the binary representation of numbers, which can be particularly useful for problems involving powers of two. The algorithm will likely involve checking the binary representation of the given number n to determine if it meets the criteria of being a power of two.

Step-by-Step Strategy

To implement the solution:

Understand the binary representation of the given number n.
Determine the condition that must be met for n to be considered a power of two in terms of its binary representation.
Use bitwise operations to check this condition efficiently.
Return True if the condition is met, indicating n is a power of two, and False otherwise.

Common Pitfalls

Incorrectly handling edge cases, such as when n is 0 or a negative number.
Failing to consider the efficiency of the algorithm, potentially leading to an overly complex or slow solution.
Not fully understanding the properties of powers of two and their binary representation.

Time & Space Complexity

The expected time complexity for an efficient solution to this problem is O(1), as it should involve a constant number of operations regardless of the size of the input n. The space complexity is also O(1), as no additional space that scales with the input size should be required.

solution.py

Python 3.13

Test results