#231 Power of Two

Easysolve on LeetCode ↗

frequently reported atGoogle Amazon

the problem

In plain words

Return true if n is a power of two, that is, n == 2ˣ for some integer x ≥ 0. Can you do it without loops or recursion?

in n = 1

out true

2⁰ = 1.

in n = 16

out true

in n = 3

out false

−2³¹ ≤ n ≤ 2³¹ − 1

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBit tricks (shift, mask, lowest set bit)

A power of two has exactly one 1-bit. Erasing it with n & (n − 1) must leave 0.

solutions

From brute force to optimal

Strip factors of two; a power of two ends at 1.

If n ≤ 0 return false.
While n is even: n /= 2.
Return n == 1.

timeO(log n)

At most 31 halvings.

spaceO(1)

In place.

java

1class Solution {2    public boolean isPowerOfTwo(int n) {3        if (n <= 0) return false;4        while (n % 2 == 0) n /= 2;5        return n == 1;6    }7}

n > 0 && (n & (n − 1)) == 0.

Reject n ≤ 0.
Check that removing the lowest 1-bit leaves nothing.

timeO(1)

Three operators.

spaceO(1)

Nothing stored.

java

1class Solution {2    public boolean isPowerOfTwo(int n) {3        return n > 0 && (n & (n - 1)) == 0; // exactly one 1-bit4    }5}

Count the 1-bits with the library.

Return n > 0 && Integer.bitCount(n) == 1.

timeO(1)

Popcount on one word.

spaceO(1)

Nothing stored.

java

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

in the room

How to say it in the interview

talk track

Clarify: n can be 0 or negative, and both answer false.
Brute: divide by 2 while n is even and check that you end at 1 — O(log n), at most 31 steps.
Optimal: a power of two has exactly one 1-bit, and n & (n − 1) erases the lowest one. So n > 0 && (n & (n − 1)) == 0.
Complexity: O(1) time and space. Mention Integer.bitCount(n) == 1 as the library version.
Test 1 (true), 0 and Integer.MIN_VALUE (both false), 2³⁰ (true) and 6 (false).

traps

Dropping n > 0: 0 and Integer.MIN_VALUE (a single 1 in the sign bit) would wrongly pass.

what they ask next

Follow-ups

Power of Four (LC 342)?

It must be a power of two whose single 1 is at an even position: n > 0 && (n & (n − 1)) == 0 && (n & 0x55555555) != 0.

before you submit

Edge cases to test

n = 0 → false.
Negative numbers → false, including Integer.MIN_VALUE, which has a single 1-bit.
2³⁰ is the largest power of two an int can hold.

practise next