Power Of Two Integers

Question

I am trying to solve a problem regarding power of two integers. The problem description is like below:

Given a positive integer which fits in a 32 bit signed integer, find if it can be expressed as A^P where P > 1 and A > 0. A and P both should be integers.
Example:
Input: n = 8
Output: true
8 can be expressed as 2^3

Input: n = 49
Output: true
49 can be expressed as 7^2

Now, I have followed below approach to solve the problem.

int Solution::isPower(int A) {
    if(A == 1)
    {
        return true;
    }
    
    for(int x = 2; x <= sqrt(A); x++)
    {
        unsigned long long product = x * x;
        
        while(product <= A && product > 0)
        {
            if(product == A)
            {
                return true;
            }
            
            product = product * x;
        }
    }
    
    return false;
}

But, I have found another solution from geeksforgeeks which is using just log divisions to find out whether the value can be expressed in power of two integers.

bool isPower(int a) 
{ 
    if (a == 1) 
        return true; 
  
    for (int i = 2; i * i <= a; i++) { 
        double val = log(a) / log(i); 
        if ((val - (int)val) < 0.00000001) 
            return true; 
    } 
  
    return false; 
}

Can anyone please explain me the above logarithmic solution? Thanks in advance.

user_14176456 · Answer

It's using maths to solve this.

9=3^2
Log 9 = log 3^2... Adding log at both side
Log 9 = 2 * log 3...using log property
2 = log 9 / log 3

As you can see the last statement is equivalent to code double val = log(a) / log(i);

Then it's checking Val - round(val) is 0...if that's true val is the ans otherwise it won't be 0. Logarithms don't give precise ans.

Power Of Two Integers

1 Answers