# 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

- find a case of x
- output:
- bool/int of 1 if we can find a combination of x
^{y}== A, else 0

- bool/int of 1 if we can find a combination of x

### 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 `x`

, we can rearrange ^{y} = A`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) * log`

, x iterates till sqrt(A) and calculating log && power both take log_{2}(A))_{2}(A) time each. - Space:
`O(1)`

, since we only ever store temporary variables.

### Recommended Posts

##### Water Flow | InterviewBit | Solution Explained

May 11, 2022