Power of Two

🎯

Power of Two

easyBIT_MANIPULATIONAmazonGoogle

Imagine you are designing a system that needs to quickly verify if a given number is a power of two, such as checking memory alignment or optimizing resource allocation.

💡 This problem tests understanding of bit manipulation, a fundamental skill in programming. Beginners often struggle because they try to use loops or division instead of leveraging binary properties that make the check very efficient.

📋

Problem Statement

Given an integer n, determine if it is a power of two. Return true if it is, and false otherwise.

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

💡

Example

Input"1"

Outputtrue

1 is 2^0, so it is a power of two.

Input"16"

Outputtrue

16 is 2^4, so it is a power of two.

Input"218"

Outputfalse

218 is not a power of two.

• 0 → false (zero is not a power of two)
• -16 → false (negative numbers are not powers of two)
• 1 → true (2^0 is 1)
• largest positive int (2^31 - 1) → false (not a power of two)

⚠️

Common Mistakes

Not handling zero and negative inputs

Returns true incorrectly for zero or negative numbers

✅ Add explicit check for n <= 0 returning false

Using n % 2 == 0 without checking n > 0

Infinite loop or incorrect results for zero or negative inputs

✅ Check n > 0 before loop

Confusing n & (n-1) trick with other bitwise operations

Incorrect results or misunderstanding of the algorithm

✅ Understand that n & (n-1) clears the lowest set bit

Using floating point division instead of integer division

Incorrect loop behavior or infinite loops

✅ Use integer division (// in Python, / in Java/C++ with ints)

Not testing edge cases like 1 or max int

Missed bugs or incorrect assumptions

✅ Always test edge cases explicitly

🧠

Brute Force (Repeated Division)

💡 This approach exists to build intuition by using a straightforward method that anyone can understand, even if it's inefficient.

Intuition

Keep dividing the number by 2 if it is even, and check if we eventually reach 1. If yes, it's a power of two; otherwise, it's not.

Algorithm

1. If n is less than or equal to 0, return false.
2. While n is greater than 1, check if n is divisible by 2.
3. If not divisible by 2, return false.
4. Divide n by 2 and continue.
5. If loop ends with n equal to 1, return true.

💡 The loop and division make the logic clear but inefficient for large numbers, which is why we look for better methods.

</>

Code

def isPowerOfTwo(n: int) -> bool:
    if n <= 0:
        return False
    while n > 1:
        if n % 2 != 0:
            return False
        n //= 2
    return True

# Driver code
if __name__ == '__main__':
    test_cases = [1, 16, 218, 0, -4]
    for num in test_cases:
        print(f'isPowerOfTwo({num}) = {isPowerOfTwo(num)}')

Line Notes

if n <= 0:Exclude zero and negative numbers early since they can't be powers of two

while n > 1:Loop until we reduce n down to 1

if n % 2 != 0:If n is not divisible by 2, it can't be a power of two

n //= 2Divide n by 2 to check the next factor

public class PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n > 1) {
            if (n % 2 != 0) return false;
            n /= 2;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] testCases = {1, 16, 218, 0, -4};
        for (int num : testCases) {
            System.out.println("isPowerOfTwo(" + num + ") = " + isPowerOfTwo(num));
        }
    }
}

Line Notes

if (n <= 0) return false;Filter out invalid inputs early

while (n > 1) {Keep dividing until n is reduced to 1

if (n % 2 != 0) return false;Check divisibility by 2 to confirm power of two

n /= 2;Divide n by 2 for next iteration

#include <iostream>
using namespace std;

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    while (n > 1) {
        if (n % 2 != 0) return false;
        n /= 2;
    }
    return true;
}

int main() {
    int testCases[] = {1, 16, 218, 0, -4};
    for (int num : testCases) {
        cout << "isPowerOfTwo(" << num << ") = " << (isPowerOfTwo(num) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

if (n <= 0) return false;Exclude zero and negative numbers immediately

while (n > 1) {Loop to reduce n to 1 by dividing by 2

if (n % 2 != 0) return false;If n is odd (except 1), it's not a power of two

n /= 2;Divide n by 2 for next iteration

function isPowerOfTwo(n) {
    if (n <= 0) return false;
    while (n > 1) {
        if (n % 2 !== 0) return false;
        n = Math.floor(n / 2);
    }
    return true;
}

// Test cases
[1, 16, 218, 0, -4].forEach(num => {
    console.log(`isPowerOfTwo(${num}) = ${isPowerOfTwo(num)}`);
});

Line Notes

if (n <= 0) return false;Filter out invalid inputs early

while (n > 1) {Keep dividing until n becomes 1

if (n % 2 !== 0) return false;Check if n is divisible by 2

n = Math.floor(n / 2);Divide n by 2 and floor to handle JS division

⏱

Complexity

TimeO(log n)

SpaceO(1)

Each iteration divides n by 2, so the number of steps is proportional to the number of bits in n.

💡 For n=16, this means about 4 divisions; for n=1,000,000, about 20 divisions.

Interview Verdict: Accepted but not optimal

This approach works but is slower than bit manipulation methods; good for understanding the problem.

🧠

Bit Manipulation Using n & (n-1)

💡 This approach leverages a classic bit trick that efficiently checks if a number is a power of two by examining its binary representation.

Intuition

A power of two has exactly one '1' bit in binary. Using n & (n-1) clears the lowest set bit. If the result is zero, n had only one set bit.

Algorithm

1. If n is less than or equal to 0, return false.
2. Compute n & (n - 1).
3. If the result is zero, return true; else return false.

💡 This uses a neat binary property that quickly identifies powers of two without loops.

</>

Code

def isPowerOfTwo(n: int) -> bool:
    if n <= 0:
        return False
    return (n & (n - 1)) == 0

# Driver code
if __name__ == '__main__':
    test_cases = [1, 16, 218, 0, -4]
    for num in test_cases:
        print(f'isPowerOfTwo({num}) = {isPowerOfTwo(num)}')

Line Notes

if n <= 0:Exclude zero and negative numbers early

return (n & (n - 1)) == 0Check if only one bit is set by clearing the lowest set bit and comparing to zero

n & (n - 1)This operation removes the rightmost set bit

== 0If result is zero, n was a power of two

public class PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;
    }

    public static void main(String[] args) {
        int[] testCases = {1, 16, 218, 0, -4};
        for (int num : testCases) {
            System.out.println("isPowerOfTwo(" + num + ") = " + isPowerOfTwo(num));
        }
    }
}

Line Notes

if (n <= 0) return false;Filter out invalid inputs

return (n & (n - 1)) == 0;Use bit trick to check if n has exactly one set bit

n & (n - 1)Removes the rightmost set bit

== 0If zero, n is a power of two

#include <iostream>
using namespace std;

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

int main() {
    int testCases[] = {1, 16, 218, 0, -4};
    for (int num : testCases) {
        cout << "isPowerOfTwo(" << num << ") = " << (isPowerOfTwo(num) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

if (n <= 0) return false;Exclude invalid inputs

return (n & (n - 1)) == 0;Check if n has exactly one set bit using bitwise AND

n & (n - 1)Clears the lowest set bit

== 0If zero, confirms power of two

function isPowerOfTwo(n) {
    if (n <= 0) return false;
    return (n & (n - 1)) === 0;
}

// Test cases
[1, 16, 218, 0, -4].forEach(num => {
    console.log(`isPowerOfTwo(${num}) = ${isPowerOfTwo(num)}`);
});

Line Notes

if (n <= 0) return false;Filter out zero and negatives

return (n & (n - 1)) === 0;Use bitwise trick to check power of two

n & (n - 1)Removes rightmost set bit

=== 0If zero, n is power of two

⏱

Complexity

TimeO(1)

SpaceO(1)

Bitwise operations run in constant time regardless of input size.

💡 This means the check is instantaneous even for very large numbers.

Interview Verdict: Accepted and optimal

This is the best approach to use in interviews for this problem.

🧠

Using Built-in Bit Count Functions

💡 This approach uses language built-ins to count set bits, which is simple and efficient but less 'algorithmic'.

Intuition

A power of two has exactly one set bit. Counting the number of set bits and checking if it equals one solves the problem.

Algorithm

1. If n is less than or equal to 0, return false.
2. Count the number of set bits in n using built-in functions.
3. Return true if count is exactly 1, else false.

💡 This approach abstracts away bit manipulation details but relies on language features.

</>

Code

def isPowerOfTwo(n: int) -> bool:
    if n <= 0:
        return False
    return bin(n).count('1') == 1

# Driver code
if __name__ == '__main__':
    test_cases = [1, 16, 218, 0, -4]
    for num in test_cases:
        print(f'isPowerOfTwo({num}) = {isPowerOfTwo(num)}')

Line Notes

if n <= 0:Exclude invalid inputs

bin(n).count('1') == 1Convert to binary string and count '1's to check if exactly one bit is set

bin(n)Converts integer to binary string representation

count('1')Counts how many bits are set

public class PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return Integer.bitCount(n) == 1;
    }

    public static void main(String[] args) {
        int[] testCases = {1, 16, 218, 0, -4};
        for (int num : testCases) {
            System.out.println("isPowerOfTwo(" + num + ") = " + isPowerOfTwo(num));
        }
    }
}

Line Notes

if (n <= 0) return false;Filter invalid inputs

return Integer.bitCount(n) == 1;Use built-in method to count set bits and check if exactly one

Integer.bitCount(n)Counts number of set bits in n

== 1True if only one bit is set

#include <iostream>
#include <bitset>
using namespace std;

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return __builtin_popcount(n) == 1;
}

int main() {
    int testCases[] = {1, 16, 218, 0, -4};
    for (int num : testCases) {
        cout << "isPowerOfTwo(" << num << ") = " << (isPowerOfTwo(num) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

if (n <= 0) return false;Exclude zero and negatives

return __builtin_popcount(n) == 1;Use GCC built-in to count set bits and check if one

__builtin_popcount(n)Counts number of set bits in n

== 1True if exactly one bit is set

function isPowerOfTwo(n) {
    if (n <= 0) return false;
    const bitCount = n.toString(2).split('0').join('').length;
    return bitCount === 1;
}

// Test cases
[1, 16, 218, 0, -4].forEach(num => {
    console.log(`isPowerOfTwo(${num}) = ${isPowerOfTwo(num)}`);
});

Line Notes

if (n <= 0) return false;Filter invalid inputs

n.toString(2)Convert number to binary string

split('0').join('').lengthCount number of '1's by removing zeros and measuring length

return bitCount === 1;Check if exactly one bit is set

⏱

Complexity

TimeO(log n)

SpaceO(log n)

Counting bits involves converting to binary or using built-ins that operate in proportion to the number of bits.

💡 For n=16, this means counting 5 bits; for large n, the count scales with bit length.

Interview Verdict: Accepted, simple but less optimal than bit trick

Good for quick coding if built-ins are allowed, but less elegant than bitwise AND trick.

📊

All Approaches - One-Glance Tradeoffs

💡 The bit manipulation approach (Approach 2) is the best choice in interviews due to its simplicity and constant time. Brute force is good for explaining the problem, and built-in functions are convenient but less elegant.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Repeated Division)	O(log n)	O(1)	No	N/A	Mention only - never code unless asked for brute force
2. Bit Manipulation Using n & (n-1)	O(1)	O(1)	No	N/A	Code this approach for optimal solution
3. Using Built-in Bit Count Functions	O(log n)	O(log n)	No	N/A	Mention if allowed, quick to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then explain the optimal bit manipulation approach clearly.

How to Present

Step 1: Clarify input constraints and edge cases like zero and negatives.Step 2: Describe the brute force approach using repeated division.Step 3: Introduce the bit manipulation trick n & (n-1) and explain why it works.Step 4: Optionally mention built-in bit count methods if allowed.Step 5: Code the optimal solution and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 5min → Test: 5min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of bit manipulation, edge case handling, and ability to optimize from brute force to constant time.

Common Follow-ups

• What if negative numbers are allowed? → They are never powers of two, so return false.
• How to check if a number is a power of four? → Check power of two and if the single set bit is in an even position.

💡 These follow-ups test deeper understanding of bit patterns and edge cases.

🔍

Pattern Recognition

When to Use

1) Problem asks if a number is a power of two or similar; 2) Input is integer; 3) Bit manipulation is allowed or expected; 4) Edge cases like zero or negatives matter.

Signature Phrases

is power of twon & (n - 1) == 0count set bits

NOT This Pattern When

Problems that require arithmetic or DP without bit tricks, e.g., Fibonacci or subset sums.

Similar Problems

Power of Three - similar concept but different baseCounting Bits - related to counting set bits in numbersNumber of 1 Bits - direct bit counting problem

Practice

1. You need to generate all possible subsets of a given set of unique integers. Which approach guarantees an optimal solution that systematically enumerates all subsets without missing or duplicating any, and can be implemented efficiently using bitwise operations?

easy

A. Greedy algorithm that picks elements based on local optimality

B. Bitmask enumeration that uses binary representation to generate all subsets

C. Dynamic programming approach similar to knapsack problem

D. Sorting the array and using two pointers to find subsets

Solution

1. Step 1: Understand the problem requires generating all subsets

   Generating all subsets means enumerating 2^n combinations, where n is the number of elements.

2. Step 2: Identify approach that systematically covers all subsets

   Bitmask enumeration uses binary numbers from 0 to 2^n - 1, where each bit represents inclusion/exclusion of an element, ensuring all subsets are generated exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets without duplicates [OK]

Hint: Bitmask maps bits to element inclusion [OK]

Common Mistakes:

• Confusing greedy or DP as suitable for subset enumeration

2. The following code attempts to count set bits for all numbers from 0 to n using Brian Kernighan's trick. Identify the line containing the subtle bug that causes incorrect results.

def countBits(n):
    res = []
    for i in range(1, n + 1):
        count = 0
        x = i
        while x:
            x &= x - 1
            count += 1
        res.append(count)
    return res

medium

A. Line 3: for i in range(1, n + 1):

B. Line 2: res = []

C. Line 5: while x:

D. Line 7: res.append(count)

Solution

1. Step 1: Check loop range correctness

   The loop starts from 1, missing 0, so the count for 0 is never computed or appended.

2. Step 2: Consequence of missing 0

   Result array length is n instead of n+1, causing mismatch and incorrect output for input including 0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Including 0 is required to match problem specification [OK]

Hint: Loop must start at 0 to include zero count [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Appending before counting
• Incorrect while condition

3. What is the time complexity of the XOR partitioning approach to find two missing numbers from 1 to n given an array of size n-2?

medium

A. O(n²) due to nested loops over the range and array

B. O(n) because it iterates over the range and array a constant number of times

C. O(n log n) due to bitwise operations on each element

D. O(1) since XOR operations are constant time

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates over the range 1 to n once and over the input array once, each in separate loops.

2. Step 2: Analyze operations inside loops

   Each iteration performs constant time XOR and bitwise operations, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two linear passes -> O(n) time [OK]

Hint: Count loops and operations per iteration carefully [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Thinking bitwise ops add log n factor
• Confusing constant time with O(1) overall

4. Identify the bug in the following code snippet for Single Number II using the bitwise FSM approach:

medium

A. Line with 'twos |= ones & num'

B. Line with 'ones ^= num'

C. Line with 'common_mask = ~(ones | twos)'

D. Line with 'ones &= common_mask'

Solution

1. Step 1: Compare common_mask calculation with correct formula

   The correct mask is the negation of the AND of ones and twos, i.e., ~(ones & twos), not ~(ones | twos).

2. Step 2: Understand impact of wrong mask

   Using OR instead of AND causes bits to be cleared incorrectly, failing to reset bits appearing thrice properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct mask uses AND, not OR, to clear bits appearing three times [OK]

Hint: Mask must clear bits appearing in both ones and twos simultaneously [OK]

Common Mistakes:

• Using OR instead of AND in mask
• Misordering bit updates

5. Suppose you want to count the number of set bits for all integers from 0 to n, but now n can be negative as well (e.g., from -n to n). Which modification to the Brian Kernighan's bit counting approach correctly handles this scenario?

hard

A. Apply the same algorithm directly to negative numbers since bitwise operations work the same.

B. Skip negative numbers because bit counting is undefined for them.

C. Convert negative numbers to their two's complement 32-bit unsigned representation before counting bits.

D. Use string conversion of the absolute value of negative numbers and count '1's.

Solution

1. Step 1: Understand bit representation of negatives

   Negative integers are represented in two's complement form, so counting bits requires interpreting them as unsigned 32-bit integers.

2. Step 2: Modify algorithm accordingly

   Convert negative numbers to their 32-bit unsigned equivalent before applying Kernighan's trick to count set bits correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two's complement conversion ensures correct bit counting for negatives [OK]

Hint: Negative bits require two's complement conversion [OK]

Common Mistakes:

• Applying algorithm directly to negatives
• Ignoring negatives
• Using absolute value without conversion