Is Power of Two easy or hard?

Power of Two is classified as an Easy problem on LeetCode. The straightforward solution uses repeated division, while the more optimal approach uses a simple bit manipulation trick. The challenge mainly tests understanding of binary representation.

How to solve Power of Two in O(1)?

Use the bit trick `n & (n - 1)`. For any power of two, the binary representation contains a single set bit. Subtracting 1 flips that bit and all lower bits, and the AND operation clears it. If `n > 0` and the result equals 0, the number is a power of two.

Power of Two Python or Java solution

In Python or Java, the typical implementation checks `n > 0 and (n & (n - 1)) == 0`. Both languages support bitwise AND operations directly, making the implementation just a single condition inside a function.

What is the best approach for Power of Two?

The bit manipulation check `n > 0 && (n & (n - 1)) == 0` is the best approach. A power of two has exactly one set bit in binary, and the expression removes the lowest set bit. If the result becomes zero, the number had only one bit set. This runs in O(1) time and O(1) space.

What data structure is used in Power of Two?

No complex data structures are required. The optimal solution relies on bitwise operations from bit manipulation. Simpler implementations may only use arithmetic operations such as division and modulo.

What is the time complexity of Power of Two?

The optimal bit manipulation solution runs in O(1) time because it performs only a few constant bit operations. The iterative or recursive division approaches run in O(log n) time since the number is repeatedly divided by 2 until it reaches 1 or becomes odd.

Is Power of Two asked at Google, Amazon, or Meta?

Power of Two is a common warm‑up question used by companies like Amazon, Google, and Meta to evaluate basic bit manipulation knowledge. It frequently appears in early interview rounds or coding screens where understanding binary representation is tested.

Description Solution Video 10:17

231. Power of Two

Easy50.5% acceptance11 companies

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⁰ = 1

Example 2:

Input: n = 16
Output: true
Explanation: 2⁴ = 16

Example 3:

Input: n = 3
Output: false

Constraints:

-2³¹ <= n <= 2³¹ - 1

Follow up: Could you solve it without loops/recursion?

Asked at 11 companies

Qualcomm Snapchat

Google Meta Bloomberg NVIDIA Amazon Microsoft

Infosys Goldman Sachs

TCS

Topics

10:17

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

231. Power of Two

Asked at 11 companies

Topics

Similar problems