Power of Four - Practice Coding Problems

Power of Four - Problem

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four if there exists an integer x such that n == 4^x.

Input & Output

Example 1 — Power of Four

$ Input: n = 16

› Output: true

💡 Note: 16 = 4², so it is a power of four

Example 2 — Not a Power of Four

$ Input: n = 5

› Output: false

💡 Note: 5 cannot be expressed as 4^x for any integer x

Example 3 — Edge Case

$ Input: n = 1

› Output: true

💡 Note: 1 = 4⁰, so it is a power of four

Constraints

-2³¹ ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n

Check Pattern

Verify if n = 4^x for some integer x

Output

Return true if it's a power of four, false otherwise

Key Takeaway

🎯 Key Insight: Powers of 4 have exactly one bit set at even positions in binary

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that powers of 4 have exactly one bit set at even positions (0,2,4,6...). Best approach is bit manipulation using masks to check the pattern. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation	O(1)	O(1)	Use bitwise operations to check the binary pattern of powers of 4
Division Method	O(log n)	O(1)	Repeatedly divide by 4 until reaching 1 or a non-divisible number
Logarithm Method	O(1)	O(1)	Use logarithms to check if log₄(n) is an integer

Bit Manipulation — Algorithm Steps

Check if n is positive and has exactly one bit set
Verify the single bit is at an even position
Use mask 0x55555555 to check even positions
Return true if both conditions are met

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Power of 2

Verify exactly one bit is set

Check Even Position

Use mask to verify bit position

Result

Both conditions must be true

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool solution(int n) {
    if (n <= 0) {
        return false;
    }
    
    // Check if n is a power of 2 (has exactly one bit set)
    if ((n & (n - 1)) != 0) {
        return false;
    }
    
    // Check if the single bit is at an even position
    // 0x55555555 = 01010101010101010101010101010101 in binary
    return (n & 0x55555555) != 0;
}

int main() {
    int n;
    scanf("%d", &n);
    
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Constant time bitwise operations

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space

✓ Linear Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler