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.
Avatar for Tanishq Chaudhary

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

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.