Leetcode 342. Power of Four

Problem

Given an integer, the task is to write a function that checks whether the given integer is a power of 4 or not. For stepping towards the solution, we have to take care of the fact that the power of any number always has a single '1' in their binary representation. So, for ensuring the input integer is a power of 4, we need to ensure two following things:

  1. It's a power of 2 (ensuring only one '1' exists in binary representation)
  2. The '1' is located at an odd position ('1' is placed at places starting from 0, 2, 4, 6, and so on for a power of 4)

For example, if the input number is 16, the binary conversion is 10000 where '1' is sitting at 4th position and it's the only 1 exists, so it is the power of 4.

If the input number is 5, the binary conversion is 101 where '1' exists at more than one position, so it's not the power of 4.

In the provided solution, we have used the built-in function __builtin_popcountll(n) which returns the number of 1s in the binary representation of the given number. By checking if its count is 1, we can assure that the given number is a power of 2.

The other condition (n - 1) % 3 == 0 ensures the '1' is located at an odd position in binary form. If you observe the power of 4 in binary representation (1, 100, 10000, 1000000,...), you'll notice that for all such numbers (n-1) is always divisible by 3.

Python Solution

1
2python
3class Solution:
4    def isPowerOfFour(self, n):
5        return n > 0 and n & (n-1) == 0 and (n - 1) % 3 == 0

Java Solution

1
2java
3public class Solution {
4    public boolean isPowerOfFour(int n) {
5        return (n > 0) && ((n & (n - 1)) == 0) && ((n - 1) % 3 == 0);
6    }
7}

JavaScript Solution

1
2javascript
3class Solution{
4    isPowerOfFour(n) {
5        return n > 0 && (n & (n - 1)) === 0 && ((n - 1) % 3 === 0);
6    }
7}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool isPowerOfFour(int n) {
6        return n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0;
7    }
8};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsPowerOfFour(int n) {
5        return n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0;
6    }
7}

In all the above solutions, bitwise AND operation '&' is used to check if 'n' (value ANDed with 'n-1') becomes zero, that would ensure that 'n' is power of 2. And if the 'n-1' is a multiple of 3, that would ensure 'n' is a power of 4.# Time and Space Complexity

The time complexity of all the above solutions will be O(1) as we are doing constant time operations. Likewise, the space complexity will also be O(1) since we are not using any extra space for performing the operations.

These solutions are highly efficient while dealing with the problem of identifying whether a number is a power of 4 or not. We are making use of some unique logical properties related to the binary representations of these specific powers, which allows us to reach the solution in constant time. These solutions can be used as a standard approach to solve the given problem in various programming languages.

Demonstrating the use of bitwise operations and modulus operations to get our answer, these solutions provide an impact of the uniqueness and might in solving some particular problems using unique bitwise properties. It also shows the importance of understanding the binary system and its significance in programming logic and algorithm efficiency.

In a nutshell, irrespective of the language one uses, the logic remains the same - using binary characteristics and bitwise manipulation to check if a given number is the power of four or not. This approach saves time and space, providing optimal solutions. The techniques applied in the solution are a great add-on to the coder's capability and improve problem-solving manners.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫