Check if a Number is a Power of 8

Problem Statement

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

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

Constraints:

• 0 ≤ n ≤ 2^31 - 1

Examples

Example 1:

Input: n = 8
Output: true

Explanation: It can be expressed as: 8 = 8^1

Example 2:

Input: n = 64
Output: true

Explanation: It can be expressed as: 64 = 8^2

Example 3:

Input: n = 16
Output: false

Explanation: 16 = 2^4, not a power of 8

Different Approaches

1️⃣ Iterative Division

Intuition:

Keep dividing the number by 8 until it becomes 1. If it’s not divisible by 8 at any step, it’s not a power of 8.

Approach:

• If n <= 0, return false
• While n % 8 == 0, divide n by 8
• At the end, check if n == 1

Code:

#include <iostream>
using namespace std;

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

int main() {
    cout << isPowerOfEight(64);  // Output: true
}

Complexity Analysis:

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

2️⃣ Bit Manipulation

Intuition:

• Power of 8 is a power of 2 where the set bit is at a position divisible by 3
• E.g., 8 = 2^3, 64 = 2^6, 512 = 2^9, ...

Approach:

• First check: n is a power of 2 → (n & (n - 1)) == 0
• Then check: number of trailing zeros % 3 == 0

Code:

#include <iostream>
using namespace std;

bool isPowerOfEight(int n) {
    if (n <= 0) return false;
    if ((n & (n - 1)) != 0) return false; // not power of 2

    // count number of 0s after set bit
    int count = 0;
    while (n > 1) {
        n >>= 1;
        count++;
    }

    return count % 3 == 0;
}

int main() {
    cout << isPowerOfEight(512);  // Output: true
}

Complexity Analysis:

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

3️⃣ Modulus

Intuition:

• All powers of 8 are powers of 2
• And: 8^k % 7 == 1 for all k ≥ 0
  So: if n is a power of 2 andn % 7 == 1 → it's a power of 8

Code:

#include <iostream>
using namespace std;

bool isPowerOfEight(int n) {
    return n > 0 &&
           (n & (n - 1)) == 0 && // power of 2
           (n % 7 == 1);
}

int main() {
    cout << isPowerOfEight(512);  // Output: true
}

Complexity Analysis:

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