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.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this