,  

Check if a number can be expressed as x^y

Problem: Given a positive integer n, find if it can be expressed as x^y where y > 1 and x > 0 and x, y both are both integers.

For example:
  • N = 125 As 125 can be written as x^y where x = 5, y = 3, so return true. 
  • N = 120 As no two integers exist for which we can write 120 = x^y, return false.
The approach to this question is simple. We have to try all numbers x starting from 2 to square root of n (given number). For every x, try x^y where y starts from 2 and increases one by one until either x^y becomes n or greater than n. 
#include <bits/stdc++.h>
using namespace std;
 
/* Returns true if n can be written as x^y */
bool isOk(int n)
{
    if (n==1)  
        return true;
 
    /* Try all numbers from 2 to sqrt(n) */
    for (int x = 2; x <= sqrt(n); x++)
    {
        int y = 2, p = pow(x, y);
 
        /* Keep increasing y while power 'p' is smaller
           than n */ 
        while (p <= n && p > 0)
        {
            if (p == n)
                return true;
            y++;
            p = pow(x, y);
         }
    }
    return false;
}

int main()
{
    int n;
    n = 125;
    cout<<isOk(n)<<"\n";

    n = 120;
    cout<<isOk(n)<<"\n";

    return 0;
}
Output: 
1
0
One optimization is to avoid calling pow() function by multiplying p with x one by one. 
#include <bits/stdc++.h>
using namespace std;

bool isOk(int n)
{
    for (int i = 2; i <= sqrt(n); i++)
    {
        int p = i;
        while(p<=n)
        {
            p*=i;
            if(p==n)
                return true;
        }
    }
    return false;
}

int main()
{
    int n;
    n = 125; 
    cout<<isOk(n)<<"\n"; 

    n = 120; 
    cout<<isOk(n)<<"\n";

    return 0;
}
Output: 
1
0
Instead of repeated multiplication, we can apply mathematical formula.

n = x^y

taking log both sides

log(n) = y*log(x)

y = log(n) / log(x)

Hence, we have to find an integer x for which RHS gives an integer y.
Algorithm:

  • Starting with i = 2, if (log a / log i) is an integer then return true. 
  • Else increment i by 1 till i < √a. 
  • If no such i is found, return false.
#include <bits/stdc++.h>
using namespace std;

/* function returns true if a number can be represented
   as x^y else return false */
bool isOk(int n)
{
    if(n==1)
        return true;

    /* we need to increment i upto sqrt(n) */
    for (int i = 2; i <= sqrt(n); i++)
    {
        double val = log(n) / log(i);

        if((val - (int)val) < 0.000000001)
        {
            return true;
        }
    }

    return false;
}

/* Driver function */
int main()
{
    int n;
    n = 125;
    cout<<isOk(n)<<"\n";

    n = 120;
    cout<<isOk(n)<<"\n";

    return 0;
}
Output: 
1
0