Power Of Two Integers | InterviewBit | Solution Explained

I explain the solution to Power of Two Integers on InterviewBit in detail. We first talk about the brute-force approach, and then build up to the optimal solution, step by step. Code in CPP and Python3. Problem Link.

0. Power Of Two Integers: Problem Discussion

0.0. IO Format

• input:
  • integer A
• condition:
  • find a case of x^y which is equal to A, given both x and y are integers and y > 1 and x > 0
• output:
  • bool/int of 1 if we can find a combination of x^y == A, else 0

0.1. Examples

• input: 4
• output: 1
• explanation: x = 2, y = 2 –> 2^2 = 4.

• input: 36
• output: 1
• explanation: x = 6, y = 2 –> 6^2 = 36

1. Power Of Two Integers: Observations & Logic

1.0. First Thoughts

Right away, we can start thinking about a brute-force solution. Since we have to find x^y and we don’t know either, we can iterate over all xs and then all ys (nested loops) and see if any combination of x ** y fits.

So, x goes in the range of [1, A) and y goes in the range of [2, ?]. Well … how do we decide the max power that y can take?

The minimum value of x is 2 (x=1 won’t care about the powers) so 2^y = A, and taking log both sides, we get: y = log(A)/log(2)

1.1. Bute-force Code [TLE]

from math import log

class Solution:
def isPower(self, A):
        for x in range(1, A):
            for y in range(2, int(log(A)/log(2)) + 1):
                if x**y == A: return 1
        return 0

1.2. Optimizing A Bit

The first thing to note is that we don’t always have to go till int(log(A)/log(2)) – this was assuming x = 2 at the worst case, but we can do better. Each time x increases, the power we have to go to also decreases! Recall that we are doing x^y. High x means y can be lower, and low x means y has to be higher – to compensate for each other.

How about doing int(log(A) / log(x))?

1.2. Optimized Brute-force [AC]

from math import log

class Solution:
    def isPower(self, A):
        if A == 1: return 1
        
        for x in range(2, A):
            for y in range(2, int(log(A)/log(x)) + 1):
                if x**y == A: return 1
        return 0

Great! We have the code accepted! But … can we do even better?

1.3. Using Math to Optimize Even More

If you realize, the entire y loop we are doing is useless. That’s because for a given x, we can directly calculate its power.

That is, when xy = A, we can rearrange y*log(X) = log(A) and then y = log(A) / log(x). Seems familiar?

But wait! We can be even smarter. The minimum value y can take is 2. This means that the maximum value x can take is … sqrt(A)! In other words, we don’t even need to iterate x in [1, A). We can do that in [1, sqrt(A)].

2. Power Of Two Integers: Optimal Implementation

2.0. Code

int Solution::isPower(int A) {
    if (A == 1) return 1;

    for (int x = 2; x <= int(sqrt(A)); x++) {
        int y = int(log(A)/log(x));
        if (pow(x, y) == A) return 1;
    }

    return 0;
}

from math import sqrt, log

class Solution:
    def isPower(self, A):
        if A == 1: return 1
        
        for x in range(2, int(sqrt(A)) + 1):
            y = int(log(A)/log(x))
            if x**y == A: return 1
        return 0

2.1. Complexity Analysis

• Time: O(sqrt(A) * log2(A)), x iterates till sqrt(A) and calculating log && power both take log₂(A) time each.
• Space: O(1), since we only ever store temporary variables.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.