Skip to main content

Math Basics

Check if an Integer is a Power of 2/3/4/5... Solution In C++/Java/Python/JS

Problem Description:

Given an integer n, check if it is a power of 2, 3, 4, 5.... Return True if it is, otherwise return False.
Illustration of Question Description

Examples:

Input: n = 16
Output: True
Explanation: 16 is a power of 2 and 4.

Input: n = 27
Output: True
Explanation: 27 is a power of 3.

Input: n = 20
Output: False
Explanation: 20 is not a power of any number.

Constraints:

  • 1 <= n <= 109

Brute Force Approach

Intuition:

In this problem, we just need to determine whether a given number, n, is a power of any number starting from 2. If it is, we return true; otherwise, we return false.

How can we check this?

Let’s take an example: Suppose n = 27, and we want to check if it’s a power of 3. We can do this by continuously dividing n by 3 until we either reach 1 or find that n is no longer divisible by 3.

  • 27 ÷ 3 = 9
  • 9 ÷ 3 = 3
  • 3 ÷ 3 = 1

Since we reached 1, we can say that 27 is a power of 3.

Now, what if n = 20?

  • 20 ÷ 3 = 6.67 (not a whole number)

Since we can't keep dividing by 3 cleanly, we know that 20 is not a power of 3.

So basically, we start with numbers like 2, 3, 4, and so on — all the way up to n - 1. For each of these numbers, we check whether the given number n can be expressed as a power of that base.

In other words, we're trying to find if there exists an integer exponent such that:

baseexponent = n

If we find even one base for which this is true, then we can say that n is a power of some integer.

If no such base works all the way up to n - 1, then it means n cannot be written as a power of any number, and we return False.

This process ensures that we thoroughly check all possible bases that could multiply by themselves multiple times to reach the number n.

Illustration of Brute Force Appraoch img1
Illustration of Brute Force Approach img2

Check if an Integer is Power of 2/3/4/5... Example

Input: n = 10
Output: False
Explanation: 10 is not a power of any number.

Step-by-step Execution:

  1. Iteration i = 2
    • isPower(10, 2) is called.
    • 10 % 2 == 0 → Divide 10 / 2 = 5.
    • 5 % 2 != 0 → Return False.
  3. Iteration i = 3
    • isPower(10, 3) is called.
    • 10 % 3 != 0 → Return False.
  5. Iteration i = 4
    • isPower(10, 4) is called.
    • 10 % 4 != 0 → Return False.
  7. Iteration i = 5
    • isPower(10, 5) is called.
    • 10 % 5 == 0 → Divide 10 / 5 = 2.
    • 2 % 5 != 0 → Return False.
  9. Iteration i = 6
    • isPower(10, 6) is called.
    • 10 % 6 != 0 → Return False.
  11. Iteration i = 7
    • isPower(10, 7) is called.
    • 10 % 7 != 0 → Return False.
  13. Iteration i = 8
    • isPower(10, 8) is called.
    • 10 % 8 != 0 → Return False.
  15. Iteration i = 9
    • isPower(10, 9) is called.
    • 10 % 9 != 0 → Return False.

This means that 10 not a power of any number from 2 to 9. Hence we return false.

Steps to write code

Step 1: Initialize the range

  • We loop through all numbers i starting from 2 up to n-1.

Step 2: Check if n is a power of i

  • For each i, we check whether n can be completely divided by i until it reaches 1.
  • If n becomes 1, it means n is a power of i, so we return true.

Step 3: Return false if no valid power is found

  • If we finish the loop without finding any i for which n is a power, return false.

Check if an Integer is Power of 2/3/4/5... Solution
Check if an Integer is Power of 2/3/4/5... solution in C++ 
class Solution {
public:
    // Function to check if n is a power of the given base
    bool isPower(int n) {
        // If n is 1 or less, return false
        if (n <= 1) return false;

        // Loop from 2 to n and check if n is a power of any i
        for (int i = 2; i < n; i++) {
            if (checkPower(n, i)) {
                return true;
            }
        }
        return false;
    }

    // Function to check if n is a power of any number from 2 to n
    bool checkPower(int n, int base) {
        // Keep dividing n by base while it is divisible
        while (n % base == 0) {
            n /= base;
        }
        // If n becomes 1, it is a powe, r of base
        return n == 1;
    }
};

Check if an Integer is Power of 2/3/4/5... solution in java 
class Solution {
    // Function to check if n is a power of the given base
    static boolean isPower(int n) {
        // If n is 1 or less, return false
        if (n <= 1) return false;

        // Loop from 2 to n and check if n is a power of any i
        for (int i = 2; i < n; i++) {
            if (checkPower(n, i)) {
                return true;
            }
        }
        return false;
    }

    // Function to check if n is a power of any number from 2 to n
    static boolean checkPower(int n, int base) {
        // Keep dividing n by base while it is divisible
        while (n % base == 0) {
            n /= base;
        }
        // If n becomes 1, it is a power of base
        return n == 1;
    }
}

Check if an Integer is Power of 2/3/4/5... solution in python 
def is_power(n):
    # If n is 1 or less, return False
    if n <= 1:
        return False

    # Loop from 2 to n and check if n is a power of any i
    for i in range(2, n):
        if check_power(n, i):
            return True
    return False

# Function to check if n is a power of any number from 2 to n
def check_power(n, base):
    # Keep dividing n by base while it is divisible
    while n % base == 0:
        n //= base
    # If n becomes 1, it is a power of base
    return n == 1

Check if an Integer is Power of 2/3/4/5... solution in javascript 
var isPower = function(n) {
    // If n is 1 or less, return false
    if (n <= 1) return false;

    // Loop from 2 to n and check if n is a power of any i
    for (let i = 2; i < n; i++) {
        if (checkPower(n, i)) {
            return true;
        }
    }
    return false;
}

// Function to check if n is a power of any number from 2 to n
var checkPower = function(n, base) {
    // Keep dividing n by base while it is divisible
    while (n % base === 0) {
        n /= base;
    }
    // If n becomes 1, it is a power of base
    return n === 1;
}

Check if an Integer is Power of 2/3/4/5... Complexity Analysis

Time Complexity: O(n log2(n))

Breakdown of the Approach

  1. We loop through all numbers from 2 to n-1.
    • This takes O(n) iterations.
  3. For each i, we repeatedly divide n by i until n becomes 1 or is no longer divisible by i.
    • This division process takes approximately O(log_i(n)) time in the worst case.

Overall Complexity

  • Since we iterate from 2 to n-1, and for each i, the worst-case division steps are O(logi(n)), the total time complexity can be approximated as: O(n⋅log⁡2(n))
  • In the worst case, when i = 2, the number of divisions per iteration is O(log2(n)).
  • Since we iterate n-1 times, multiplying both gives O(n log2(n)).

Space Complexity: O(1)

Auxiliary Space Complexity (Extra Memory Used)

  • The algorithm does not use any extra data structures such as arrays, hash maps, or recursion stacks.
  • The function isPower(n, base) only uses a few integer variables (n and base), which are constant space O(1).
  • The function checkPower(n) also only uses a loop variable (i), which is also O(1).
  • Thus, the auxiliary space complexity is O(1).

Total Space Complexity

  • Total space complexity includes both input storage and auxiliary space.
  • Since we are only storing n (which is a single integer) and no extra arrays or recursion stacks are used, the total space complexity remains O(1).

Final Complexity

  • Auxiliary Space: O(1)
  • Total Space: O(1)

Is the brute force approach efficient?

The constraint on n is up to 109. The complexity of the brute force approach is O(n × log(n)).

We can clearly say that O(n) itself is not efficient as the constraints go up to 109. Hence, we need to optimize our solution.

Optimal Approach

Intuition:

In our previous approach, the main factors affecting time complexity were:

  1. Looping from 2 to n-1, which takes O(n) time.
  2. Repeatedly dividing n by i, which takes around O(logi(n)) time.

This results in a high overall complexity, making our approach inefficient for large numbers.

Can we do better?

Instead of looping all the way up to n, we only loop up to the square root of n.

Why stop at √n?

Let’s think logically:

  • Any number greater than √n would have its square (x²) greater than n.
  • This means n can't be a power of any base larger than √n.
  • Therefore, checking numbers up to √n is sufficient.

This reduces the loop iterations from O(n) → O(√n), which is a big improvement!

Check if an Integer is Power of 2/3/4/5... Algorithm

However, there’s also a smarter way to check if n is a power of a given number without repeatedly dividing it.

Using Logarithms for Faster Calculation

Instead of manually dividing n by i multiple times, we can use logarithms to check in just O(1) time!

Understanding the Logarithm Trick

We need to check if n is a power of some number i. That means we want to find:

ix = n

for some integer x. Taking the logarithm base 10 (log) on both sides:

ln(ix) = ln(n)

Using properties of logarithms, this gives us:

xln(i) = ln(n)

Finally solving for x:

x = ln(n) / ln(i)

If x is an integer, then n is a power of i!

Example:

Checking if n = 27 is a power of i = 3

  • Compute ln(27) / ln(3): ln⁡(27) / ln⁡(3) → 3.295 / 1.099 → 3.0
  • Since 3.0 is a whole number, 27 is a power of 3

Now, what if n = 20?

  • Compute ln(20) / ln(3): ln⁡(20) / ln⁡(3) → 2.996 / 1.099 → 2.73
  • Since 2.73 is not an integer, 20 is NOT a power of 3

Why is this better?

  • No need for repeated division → Instead of checking by dividing n again and again, we can compute a logarithm in O(1) time.
  • Faster approach → The loop still runs O(√n) times, but the expensive O(logi(n)) factor is removed!

To check if the computed logarithm value is an integer, we use the difference method. Instead of relying on direct equality (which can be inaccurate due to floating-point precision errors), we compare the absolute difference between the computed logValue and its rounded version.

How It Works:

  1. Compute logValue as ln(n) / ln(i), which gives the exponent needed to express n as a power of i.
  2. Use the round function, which rounds the value to the nearest whole number.
  3. Check if the absolute difference between logValue and its rounded version is small enough (less than 10-9).

Why Use abs(logValue - round(logValue)) < 1e-9?

Computers store decimal numbers as floating-point values, which are not always perfectly precise due to rounding errors.
For example, log3(9) might not give exactly 2.000000, but instead something like 2.0000000001.

If we check using floor(logValue) == logValue, small rounding errors might cause false results.
Instead, we use this check:

∣logValue−round(logValue)∣<10−9

This means:

  • If logValue is very close to an integer (within 0.000000001), we treat it as an integer.
  • If it's not, we reject it.

Example:

  • log3(9) = 2.0000000001 → abs(2.0000000001 - 2) = 0.0000000001 (Power)
  • log_3(10) = 2.0901 → abs(2.0901 - 2) = 0.0901 (Not a power)

By using logarithms, we significantly optimize our approach while keeping the logic simple and easy to implement.

Let us understand this with a video,

0:00
/1:17

Illustration of Optimal Approach Animation

Check if an Integer is Power of 2/3/4/5... Example

Input: n = 10
Output: False
Explanation: 10 is not a power of any number.

Step-by-Step Execution:

Step 1: Initialization

  • Given n = 10, we loop from i = 2 to sqrt(10) ≈ 3.16 (i.e., i = 2, 3).
  • The function uses log(n) / log(i) to check if n is a power of i.

Step 2: Check for i = 2

Compute:

  • log2(10) = ln(10) / ln(2)
  • = 2.302 / 0.693
  • ≈ 3.32

Check Integer Condition:

  • We use abs(logValue - round(logValue)) < 1e-9
  • abs(3.32 - round(3.32)) = abs(3.32 - 3) = 0.32
  • Since 0.32 ≥ 1e-9, log2(10) is not an integer
    Conclusion: 10 is not a power of 2.

Step 3: Check for i = 3

Compute:

  • log3(10) = ln(10) / ln(3)
  • = 2.302 / 1.099
  • ≈ 2.09

Check Integer Condition:

  • abs(logValue - round(logValue)) < 1e-9
  • abs(2.09 - round(2.09)) = abs(2.09 - 2) = 0.09
  • Since 0.09 ≥ 1e-9, log3(10) is not an integer
    Conclusion: 10 is not a power of 3.

Final Output:

  • We exit the loop because i has reached sqrt(n).
  • Since no valid power was found, return False.

Steps to write code

Step 2: Initialize Variables

  • Read the input number n.
  • If n is 1, return False immediately (since 1 is not considered a power of any number).
  • Define a loop to iterate over potential bases from 2 to sqrt(n), since any base greater than sqrt(n) will have its square exceeding n.

Step 3: Loop Through Potential Bases

  • Iterate i from 2 to sqrt(n).
  • For each i, calculate logi(n) using the formula.
    log base i of n = natural log of n divided by natural log of i
    logi(n) = ln(n) / ln(i)

Step 4: Check If logi(n) is an Integer

  • Since logarithmic calculations may result in slight precision errors, check if logi(n) is an integer using:
    absolute difference between logi(n) and its nearest integer is very small
    abs(logi(n) - round(logi(n))) < 10-9
  • If this condition holds true for any i, return True immediately.

Step 5: Return the Result

  • If the loop completes without finding any valid base i, return False.

Check if an Integer is Power of 2/3/4/5... leetcode solution
Check if an Integer is Power of 2/3/4/5... solution in C++ 
class Solution {
public:
    bool isPower(int n) {
        if (n <= 1) return false;

        for (int i = 2; i <= sqrt(n); i++) {
            // Compute log base i of n
            double logValue = log(n) / log(i);

            // Check if logValue is an integer using a more precise method
            if (abs(logValue - round(logValue)) < 1e-9) {
                return true;
            }
        }
        return false;
    }
};

Check if an Integer is Power of 2/3/4/5... solution in java 
class Solution {
    // Function to check if n is a power of any base from 2 to sqrt(n)
    static boolean isPower(int n) {
        if (n <= 1) return false;

        for (int i = 2; i <= Math.sqrt(n); i++) {
            // Compute log base i of n
            double logValue = Math.log(n) / Math.log(i);

            // Check if logValue is an integer using a more precise method
            if (Math.abs(logValue - Math.round(logValue)) < 1e-9) {
                return true;
            }
        }
        return false;
    }
}

Check if an Integer is Power of 2/3/4/5... solution in python 
def is_power(n):
    if n <= 1:
        return False

    for i in range(2, int(math.sqrt(n)) + 1):
        # Compute log base i of n
        log_value = math.log(n) / math.log(i)

        # Check if log_value is an integer using a more precise method
        if abs(log_value - round(log_value)) < 1e-9:
            return True

    return False

Check if an Integer is Power of 2/3/4/5... solution in javascript 
var isPower = function(n) {
    if (n <= 1) return false;

    for (let i = 2; i <= Math.sqrt(n); i++) {
        // Compute log base i of n
        let logValue = Math.log(n) / Math.log(i);

        // Check if logValue is an integer using a more precise method
        if (Math.abs(logValue - Math.round(logValue)) < 1e-9) {
            return true;
        }
    }
    return false;
}

Check if an Integer is Power of 2/3/4/5... Complexity Analysis

Time Complexity: O(√n)

The code efficiently checks if n is a power of any number from 2 to sqrt(n) using logarithms. Let’s break down the time complexity in detail.

Looping from 2 to sqrt(n)

  • The outer loop runs from 2 to floor(sqrt(n)).
  • The number of iterations is approximately O(√n).

Computing Logarithms

  • For each iteration, we compute log_i(n) = ln(n) / ln(i).
  • Computing the natural logarithm (ln) of a number in most programming languages takes O(1) time.
  • Since we perform O(1) operations per loop iteration, the total logarithm computation across all iterations is O(√n) × O(1) = O(√n).

Checking if log_i(n) is an Integer

  • We compare logi(n) with its rounded value and check if the absolute difference is less than 10-9.
  • This comparison is a constant-time operation O(1) for each i.
  • Since we do this for every i from 2 to sqrt(n), the total cost is O(√n) × O(1) = O(√n).

Final Complexity Calculation

Each iteration performs O(1) work (logarithm computation + integer check), and there are O(√n) iterations.
Thus, the overall time complexity is: O(√n)

Space Complexity: O(1)

In our optimized approach, we need to analyze both auxiliary space complexity and total space complexity.

Auxiliary Space Complexity

Auxiliary space refers to the extra memory used by the algorithm beyond the input itself.

  • The function isPower(n, base):
    • Stores a floating-point variable logValue, which takes O(1) space.
    • Performs calculations using logarithms, but these do not require extra memory.
  • The loop in checkPower(n):
    • Runs from 2 to sqrt(n), but it only uses a few constant-sized variables (i, n, boolean flag).
    • This results in O(1) auxiliary space.

Thus, the auxiliary space complexity is O(1) since we do not use any additional data structures like arrays or lists.

Total Space Complexity

Total space includes both input size and auxiliary space.

  • Input size: We take a single integer n, which is O(1).
  • Auxiliary space: As discussed, it's O(1).

Thus, the total space complexity remains O(1).

Similar questions

Now we have successfully tackled this problem, let's try these similar problems:-

1. Perfect Squares

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

2. Finding Position

Some people(n) are standing in a queue. A selection process follows a rule where people standing on even positions are selected. Of the selected people a queue is formed and again out of these only people on even position are selected. This continues until we are left with one person. Find out the position of that person in the original queue.