Power of Four Solution in Java

Problem Description

So, you think you can just throw any number at the wall and see if it sticks as a power of four? Well, think again! The “Power of Four” problem on LeetCode is here to remind you that not all numbers are created equal. A number is a power of four if it can be expressed as 4ⁿ where n is a non-negative integer. In simpler terms, if you can’t find a way to express your number as 1, 4, 16, 64, or any other number that looks like it’s been to a math party, then it’s not a power of four.

Imagine you’re at a party, and everyone is dancing in groups of four. If you can’t find a way to join a group, you’re just standing awkwardly in the corner. That’s what it feels like for numbers that aren’t powers of four!

Code Solution

Here’s the Java solution that will help you determine if a number is a power of four:


class Solution {
  public boolean isPowerOfFour(int n) {
    return n > 0 && Integer.bitCount(n) == 1 && (n - 1) % 3 == 0;
  }
}

Approach

The approach used in this solution is quite clever. It checks three conditions:

The number n must be greater than zero.
The number must have exactly one bit set in its binary representation (which means it’s a power of two).
The number minus one must be divisible by three, which is a neat trick to ensure it’s a power of four.

This combination of checks ensures that we only return true for numbers that are indeed powers of four.

Time and Space Complexity

Time Complexity: O(1) – The solution runs in constant time since it only involves a few arithmetic operations and bit manipulation.
Space Complexity: O(1) – No additional space is used that scales with input size.

Real-World Example

Think of the “Power of Four” problem like a game of musical chairs. If you’re not in a group of four, you’re out! Just like how only numbers that can be expressed as 4ⁿ get to stay in the game. For instance, the number 16 is a power of four because it can be expressed as 4². But 10? Sorry, buddy, you’re out of the game!