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.

Problem:

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.

 

Solution:

bool Solution::isPower(int n) {
if(n==1)
return true;
for(int i=1;i<=sqrt(n);i++)
{
for(int j=2;j<=log2(n);j++)
{
if(pow(i,j)==n)
return true;
}
}
return false;
}

time complexity:O(sqrt(n)*log(n))

Leave a Reply

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