Problem Statement

Given an integer n, check whether it is a power of 16.

A number is a power of 16 if it can be expressed as 16^k, where k is a non-negative integer.

Constraints

• 0 ≤ n ≤ 2^31 - 1 (i.e., n is a 32-bit signed integer)

Examples

Example 1:

Input: n = 16
Output: true

Explanation: 16 = 16^1

Example 2:

Input: n = 256
Output: true

Explanation: 256 = 16^2

Example 3:

Input: n = 64
Output: false

Explanation: 64 = 2^6, not a power of 16

Different Approaches

1️⃣ Iterative Division

Intuition:

Keep dividing the number by 16. If it’s not divisible at any point, it’s not a power of 16. If it becomes 1, it is.

Approach:

1. If n <= 0, return false
2. While n % 16 == 0, divide n by 16
3. Return true if n == 1

Code:

#include <iostream>
using namespace std;

bool isPowerOfSixteen(int n) {
    if (n <= 0) return false;
    while (n % 16 == 0) {
        n /= 16;
    }
    return n == 1;
}

int main() {
    cout << isPowerOfSixteen(256);  // Output: true
}

Complexity Analysis:

• Time Complexity:O(log 16(n))
• Space Complexity:O(1)

2️⃣ Bit Manipulation

Intuition:

All powers of 16 are powers of 2, specifically 2^0, 2^4, 2^8, 2^12, etc.
So:

1. It must be a power of 2 → only 1 bit set
2. The position of the set bit must be a multiple of 4

Approach:

1. Check if n is a power of 2: (n & (n - 1)) == 0
2. Count the position of the set bit (i.e., trailing zeros)
3. Return true if that position is divisible by 4

Code:

#include <iostream>
using namespace std;

bool isPowerOfSixteen(int n) {
    if (n <= 0 || (n & (n - 1)) != 0) return false;

    int count = 0;
    while (n > 1) {
        n >>= 1;
        count++;
    }

    return count % 4 == 0;
}

int main() {
    cout << isPowerOfSixteen(256);  // Output: true
}

Complexity Analysis:

• Time Complexity:O(log n)
• Space Complexity:O(1)

3️⃣ Modulus Based Trick

Intuition:

• Powers of 16 are powers of 2 with their bit set a multiples of 4
• You can also use n % 15 == 1 as a mathematical property, but it's less robust than bit checks.

Code:

#include <iostream>
using namespace std;

bool isPowerOfSixteen(int n) {
    return n > 0 &&
           (n & (n - 1)) == 0 && // power of 2
           (n % 15 == 1);        // only true for powers of 16
}

int main() {
    cout << isPowerOfSixteen(256);  // Output: true
}

Complexity Analysis:

• Time Complexity:O(1)
• Space Complexity:O(1)