[InterviewBit]Power Of Two Integers

Question

this is the question: 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.

I know that I can solve it using brute-force method; however, I am wondering if I could solve it in a better way, or can I solve it using recursion technique? Thanks for your kind help!

@Maharaj My biggest concern is that if this problem can be solved using recursion? — Chih-Yu Yeh, Aug 11 '16 at 11:45
Can you include some pseudocode that you tried to arrive at solution? — Rupsingh, Aug 11 '16 at 11:48
Possible duplicate of [Finding whether a number has P^Q form or not?](http://stackoverflow.com/questions/33066757/finding-whether-a-number-has-pq-form-or-not) — Spektre, Aug 12 '16 at 07:20

score 4 · Accepted Answer · edited Aug 11 '16 at 12:26

4

One approach is to convert to double, and use math to obtain fractional powers of 1/2, 1/3, 1/4, and so on, up to 1/log2 n. The result would be an A; the denominator of the fraction would be P.

Since the computation of the power is in doubles, you would need to try both ceil and floor of the result. Once you hit zero without finding a result, the algorithm could stop.

edited Aug 11 '16 at 12:26

xenteros

15,586
12
56
91

answered Aug 11 '16 at 11:41

Sergey Kalinichenko

714,442
84
1,110
1,523

@xenteros You gave him the same exact solution :-) – Sergey Kalinichenko Aug 11 '16 at 12:21
@xenteros Regardless of when you stop, the approach is identical, as in "no difference whatsoever". – Sergey Kalinichenko Aug 11 '16 at 12:23

score 3 · Answer 2 · answered Apr 24 '17 at 05:05

3

This can also be solved this way.

public boolean isPower(int a) {
    if (a == 1) return true;
    for (int idx = 2; idx * idx <= a; idx ++) {
        double val = Math.log (a)/Math.log (idx);
        if ((val - (int) val) < 0.00000001) return true;
    }
    return false;
}

answered Apr 24 '17 at 05:05

Blackpirate

31
3

6

Why only 0.00000001 ? – Gaurang Singhal Jul 13 '17 at 12:48
Can you please explain the approach? – Setu Kumar Basak Aug 30 '20 at 14:33

HeadAndTail · Answer 3 · 2018-01-20T14:21:34.137

0

we will check if a == 1 then it can be represented as x ^ 0 hence true . for a > 1 we will check for either 2 or 3 or 4....a; we will divide p (p = a) if p % 2 or ,3 or ,4 or ....... if(p==1) means p is completely divisible by either 2, or 3, or 4 , ...... . means p (where p = a) can we written as x ^ y. hence return true.

 public boolean isPower(int a) {
       if(a==1) return true;
         for (int i = 2; i*i <= a; i++) {
              int p = a;
              while(p%i == 0){
                p/=i;
              }
              if(p == 1) return true;
         }
         return false;

  }

edited Jan 20 '18 at 14:21

answered Jan 20 '18 at 13:45

HeadAndTail

804
8
9

Please explain you solution briefly. Code-only answers are less useful and must be avoided. – Eduard Malakhov Jan 20 '18 at 14:12

score 0 · Answer 4 · answered Dec 03 '18 at 09:54

Code based on @xenteros Answer and a successful submission .

public static int isPower(int A) {
        if(A == 1)
            return 1;
        double Ad = A ;
       for(int i =2;i<=(Math.log(Ad)/Math.log(2));i++)
       {
           double a = Math.pow(Ad,(double)1/i);
           if(Math.ceil(a) == Math.floor(a) || Math.ceil(a)-a <0.000000001)
                return 1;
       }
       return 0;
    }

score 0 · Answer 5 · answered Jul 02 '19 at 15:00

0

while(test--)
{
    int input;
  cin>>input;

  if(input<=2)
  {cout<<"0"<<endl;
  break;}
  //cout<<m;
  int m=sqrt(input);
  int count=2;
  int flag=0;
while(count<=m+1)
{
    if(ceil(log2 (input)/log2 (count))== floor(log2 (input)/log2 (count)))
    {
       // cout<<"ghusa   "<<count<<"  "<<input;
        flag=1;
        cout<<"1";
        break;
    }
    count++;
}
if(flag==0)
{cout<<"0";

}
cout<<endl;  
}

return 0;

}

answered Jul 02 '19 at 15:00

viman ch das

1
1
1

Please describe, what was the problem, and how will this snippet solve it, to help others understand this answer. Additionally, the question is more than 2 years old and has an accepted answer... – FZs Jul 02 '19 at 15:26

score 0 · Answer 6 · edited Jul 02 '19 at 17:33

0

bool ans(long long int n)
{
    if(n==1)
        return true;
    else
    {
        for (long long int i = 2; i*i <= n; i++)
        {
            if(ceil(log2 (n)/log2 (i)) == floor(log2 (n)/log2 (i)))
            {
                return true;
            }
        }
    }

    return false;
}

edited Jul 02 '19 at 17:33

Bùi Đức Khánh

3,975
6
27
43

answered Jul 02 '19 at 15:15

viman ch das

1
1
1

score -1 · Answer 7 · answered Aug 11 '16 at 11:53

Lets call the initial integer N.

First, you must get all the prime divisors of N.

If N has just 1 divisor, that it is in the form D^k, so it's true.

If it has more than 1 divisor, you should check if the gcd of the number of each divisor is different from 1 and is even.

For example:

12 = 2 * 2 * 3
not possible, GCD(2,1) = 1

24 = 2 * 2 * 2 * 3
not possible, GCD(3,1) = 1

36 = 2 * 2 * 3 * 3
possible,     GCD(2,2) = 2

144 = 2 * 2 * 2 * 2 * 3 * 3
possible,     GCD(4,2) = 2

120 = 2 * 2 * 2 * 3 * 5
not possible, GCD(1,1,3) = 1

216 = 2 * 2 * 2 * 3 * 3 * 3
not possible, GCD(3,3) = 3

[InterviewBit]Power Of Two Integers

7 Answers7