DSA SheetEasy
EditorialPractice

RECURSION & BACKTRACKING › RECURSION PROBLEMS

Power of Two

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe binary pattern behind powers of two

A power of two is formed by placing one 1 in a binary number and filling every other position with 0. For example, 1 is 0001, 2 is 0010, 4 is 0100, and 16 is 10000. Every positive power of two therefore has exactly one set bit.

Subtracting 1 from a number with one set bit clears that bit and turns every bit to its right into 1. Thus n and n - 1 have no set bit in the same position when n is a power of two, so their bitwise AND is zero. Any positive number with at least two set bits shares one of them with n - 1, making the AND nonzero.

the binary forms of a power of two and nearby non-powersThe figure compares binary rows for 16 and 15, followed by 12 and 11. The row for 16 is 10000 and the row for 15 is 01111, so their only possible 1 bits are in different positions and their AND is 0. The row for 12 is 01100 and the row for 11 is 01011, so they share a 1 bit and their AND is nonzero. The comparison makes the one-set-bit test visible.10000011110110010000 AND 01111 = 00000 (0)01100 AND 01011 = 01000 (8)Binary forms: powers of two and nearby non-powersn = 16power of twon − 1 = 15n = 12non-powerbitwise AND compares the set bits in commonA power of two shares no set bit with the number immediately before it; a positivenon-power does.

Approach

  1. Reject n <= 0 first, because zero has no set bit and negative integers are not powers of two under the problem's definition; this guard also prevents the bit test from accepting an invalid value.
  2. Compute n & (n - 1), which removes the lowest set bit from n while leaving all higher bits unchanged; this is the operation that exposes whether another set bit remains.
  3. Return true exactly when the AND result is zero, because a positive number reaches zero after clearing its only set bit only when it started with exactly one set bit.
  4. Use short-circuit evaluation in n > 0 && ..., so n - 1 is evaluated only for positive n; this keeps the invalid cases out of the bit manipulation and avoids signed boundary trouble.

Complexityone bit operation and no auxiliary structure

MEASUREBOUNDWHY
TimeO(1)The expression performs one subtraction and one bitwise AND, regardless of how many binary positions n has. There is no loop or repeated scan.
SpaceO(1) extraThe solution stores only the input and a constant number of intermediate values. The returned boolean is required output and is excluded from the extra-space bound; the bound does not degrade for any allowed input shape.
Here n is the input integer; output storage for the returned boolean is excluded from extra space.

Annotated solutionC++ · bit test · the constant-time version

CPPTest positivity, then check whether clearing the lowest set bit leaves zero.
#include <vector>

using namespace std;

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

The order of the two conditions matters. C++ evaluates && from left to right and stops when the left side is false, so zero and negative inputs never reach n - 1. For a positive n, the second condition is exactly a one-set-bit check: removing that bit leaves zero only if no other 1 remains.

The arithmetic alternativea readable division loop, at the cost of logarithmic time

CPPRepeatedly divide by two and accept only when the remaining factor is one.
#include <vector>

using namespace std;

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;

        while (n % 2 == 0) {
            n /= 2;
        }

        return n == 1;
    }
};

This is a different arrangement, not an optimisation. It repeatedly removes factors of two, so it takes O(log n) iterations in the largest positive case, while the bit test takes O(1) time. It uses O(1) extra space and can be easier to justify without bitwise knowledge, but the bit identity is the more direct fit for this problem.

Common mistakestwo wrong code shapes that survive simple tests