What happens if you checking only if n is a power of two?

Returns true for powers of two that are not powers of four, e.g., 8 Fix: Add mask check to ensure the set bit is at an even position

What happens if you using floating point equality for log checks without tolerance?

Fails for some inputs due to floating point precision errors Fix: Avoid floating point checks or use bit manipulation instead

What happens if you not handling zero and negative inputs?

Incorrectly returns true or causes errors Fix: Explicitly check and return false for n <= 0

What happens if you using loops or recursion when problem states no loops?

Fails interview requirement or inefficient solution Fix: Use bit manipulation for constant time solution

Interview Prepbit-manipulationeasyAmazonGoogle

Power of Four

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

Power of Four

easyBIT_MANIPULATIONAmazonGoogle

Imagine you are designing a system that needs to quickly verify if a given number represents a perfect power of four, which is crucial for optimizing memory alignment in hardware.

💡 This problem tests understanding of bit manipulation and number properties. Beginners often struggle because they try to use loops or math functions instead of leveraging binary patterns that uniquely identify powers of four.

📋

Problem Statement

Given an integer n, determine if it is a power of four. Return true if it is, otherwise return false. Input: integer n. Output: boolean indicating if n is a power of four.

-2^31 <= n <= 2^31 - 1You must solve it without using loops or recursion.

💡

Example

Input"16"

Outputtrue

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

Input"5"

Outputfalse

5 is not a power of four.

0 → false (zero is not a power of four)
1 → true (4^0 = 1)
-4 → false (negative numbers cannot be powers of four)
Integer max value (2^31 - 1) → false (not a power of four)

⚠️

Common Mistakes

Checking only if n is a power of two

Returns true for powers of two that are not powers of four, e.g., 8

✅ Add mask check to ensure the set bit is at an even position

Using floating point equality for log checks without tolerance

Fails for some inputs due to floating point precision errors

✅ Avoid floating point checks or use bit manipulation instead

Not handling zero and negative inputs

Incorrectly returns true or causes errors

✅ Explicitly check and return false for n <= 0

Using loops or recursion when problem states no loops

Fails interview requirement or inefficient solution

✅ Use bit manipulation for constant time solution

🧠

Brute Force (Iterative Division)

💡 This approach exists to build intuition by directly checking the definition of power of four through repeated division, which is straightforward but inefficient.

Intuition

Repeatedly divide the number by 4 if it is divisible until it becomes 1. If at any point it is not divisible by 4, return false.

Algorithm

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

💡 This algorithm directly follows the mathematical definition but can be slow for large inputs.

</>

Code

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

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

Line Notes

if n <= 0:Negative numbers and zero cannot be powers of four

while n != 1:Loop until we reduce n to 1 if it is a power of four

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

n //= 4Divide n by 4 to peel off one power layer

public class PowerOfFour {
    public static boolean isPowerOfFour(int n) {
        if (n <= 0) return false;
        while (n != 1) {
            if (n % 4 != 0) return false;
            n /= 4;
        }
        return true;
    }

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

Line Notes

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

while (n != 1)Keep dividing until n becomes 1

if (n % 4 != 0) return false;Check divisibility by 4 at each step

n /= 4;Reduce n by dividing by 4

#include <iostream>
using namespace std;

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

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

Line Notes

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

while (n != 1)Loop until n is reduced to 1

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

n /= 4;Divide n by 4 to check next power

function isPowerOfFour(n) {
    if (n <= 0) return false;
    while (n !== 1) {
        if (n % 4 !== 0) return false;
        n = n / 4;
    }
    return true;
}

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

Line Notes

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

while (n !== 1)Keep dividing until n becomes 1

if (n % 4 !== 0) return false;If not divisible by 4, return false

n = n / 4;Divide n by 4 to check next power

⏱

Complexity

TimeO(log n)

SpaceO(1)

Each division reduces n by a factor of 4, so the loop runs about log4(n) times, which is O(log n).

💡 For n=16, this means about 2 divisions; for n=1,000,000, about 10 divisions.

Interview Verdict: Accepted

This approach works but is not the most efficient or elegant for bit manipulation problems.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Iterative Division)	`O(log n)`	`O(1)`	No	N/A	Mention only - never code
2. Bit Manipulation Using Power of Two Check and Bitmask	`O(1)`	`O(1)`	No	N/A	Code this approach
3. Using Logarithm and Math Checks	`O(1)`	`O(1)`	No	N/A	Mention as alternative, but not recommended

Practice

(1/5)

1. You need to compute the number of set bits (1s) in the binary representation of every integer from 0 up to a given number N efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Use Brian Kernighan's bit counting trick to count set bits for each number by repeatedly clearing the least significant set bit.

B. Use a dynamic programming approach that counts bits by building results from smaller subproblems using right shifts.

C. Use a greedy approach that counts bits by checking each bit position independently for all numbers.

D. Convert each number to a binary string and count the '1' characters using built-in string functions.

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand the problem requirements

Step 2: Evaluate approaches for optimality

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that uses bitmasking

Final Answer:

Quick Check:

Solution

Step 1: First call getSum(1, 2)

Step 2: Since carry is 0, return sum_ = 3

Final Answer:

Quick Check:

Solution

Step 1: Analyze initialization of result

Step 2: Understand correct initialization

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse of words

Step 2: Modify approach

Step 3: Why other options fail

Final Answer:

Quick Check:

Ready to prove it?