# 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 xy 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 xy == 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 xy 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 2y = 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 xy. 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 log2(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.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

1. Srishti Chopra :July 23, 2022 at 11:29 am

2. Makarand :August 16, 2022 at 11:06 am
3. Gopal :November 14, 2022 at 5:53 pm