CareerCup

Perfect powers in linear time?

boolean isPerfectPower(int n) {
	
		for (int i = 1; i < n; i++) { 
		
			double temp = Math.log(n)/Math.log(i);
			
			if (Math.ceiling(temp) == temp) { return true;}
		}

		return false;
	}

Simple one -

Find all the prime factors of the number 'N'. If they occur in sets (or) if all the prime factors are same, then it can be expressed in form p^q.

Example : N=216, factors = {2,2,2,3,3,3}. here every prime factor has its set (i.e. {2,3} ) which is repeated, hence it can be represented in P^q format which is (2*3)^3 i.e. Product of numbers in every Set raised to the power of number of such sets.

If N=32 with prime factors (2,2,2,2,2) all are same, hence true

Bug in question. Every number can, right? n = n ^ 1, where n and 1 are integers.

The idea is :
1. Factorize the no *n* into prime factors.
2. Now a factorisation is a list of ( prime, multiplicity ) pair. Check that if all the multiplicity values has a GCD >1.
See the code from here : [question?id=5742470735331328]

// ZoomBA
def gcd( a,b ){ // copied from wikipedia 
  while ( b != 0 ){
    t = b ; b = a % b ; a = t  
  } 
  return a 
}

def is_expressible( n ){
  multiplicities =  select ( lfold ( [2:n+1] , dict() ) -> { 
    continue ( exists ( $.p.keySet ) :: {  $.o /? $.$.o } )
    $.p[$.o] = 0  
    for ( x = n ; $.o /? x ; x/= $.o ){ $.p[$.o] += 1 } 
    $.p 
  } ) :: { $.o.value > 0 } -> { $.o.value }
  // calculate gcd of all the multiplicities
  final_gcd = reduce ( multiplicities ) -> { gcd( $.p , $.o ) }
  final_gcd > 1 // for a non trivial solution 
}

cr.yp.to/papers/powers.pdf
here is an algorithm that interviewer wanted to hear

import java.util.Random;
import java.util.Scanner;


public class PerfectPower {
	public static void main(String[] args) {
		int N;
		Scanner sc = new Scanner(System.in);
		N = new Random().nextInt(Integer.MAX_VALUE);
		System.out.println(isPerfectPower(N));
		sc.close();
	}
	
	static boolean isPerfectPower(int N){
		int limit = (int)Math.sqrt(N);
		for(int j = limit;j>=2;j--){
		//for(int j = 2;j<=limit;j++){
			int num =N;
			while(num%j==0 && num>1)num=num/j;
			if(num==1)
				return true;
		}
		return false;
	}
}

C#, Assumption:input number is a positive integer
----------------------------------------------------------------
///



bool IsPower(int num)
{
if (num <= 3) return false;

IList<int> primeList = new List<int>();
int count = 0;
while(num % 2 == 0)
{
num /= 2;
count++;
}

if (count != 0) primeList.Add(count);

for(int i = 3; i <= num; i += 2)
{
count = 0;
while(num % i == 0)
{
num /= i;
count++;
}

if (count != 0) primeList.Add(count);
}

if (primeList.Count() == 0) return false; // a prime number which is greater than 3

using (var enumerator = primeList.GetEnumerator())
{
enumerator.MoveNext();
var current = enumerator.Current;

if (current == 1) return false;

while(enumerator.MoveNext())
{
if (current != enumerator.Current) return false;


}
}

return true;
}

\\\

boolean canBeExpressedInP&Q(int N){

          int [] array=new int[(int)Math.sqrt(N)];// create array to count the number of prime factor.
          int n=N;
          Arrays.fill(array,0);// fill with zero
          for(int i=2;i<=Math.sqrt(N);i++){          // N=216=> 2*108(N=108) that's why Math.sqrt(N)
                while(N%i==0){
                     array[i]++;// count number of prime like 216=2*2*2*3*3*3, array[2]=3 and array[3]=3
                     N=N/i;      // divide N every time we get any prime factor                 
                }
          }
          //Now check array if all elements are equal excluding zero element.
          int max=0;
          for(int i=2; i<sqrt(n);i++){
                if(array[i]!=0 && max==0){// first time max is initialize with 3, for N=216,
                      max=array[i];
                }
                else if(array[i]!=0 && array[i]!=max){
                        return false;
                }
          }// end of for loop., array[0]=0, array[1]=0, array[2]=3, array[3]=3;
          return true;
      }

bool pq(int n)
{
    int i = 2;
    std::map<int, int> counts;

    if (n < 0)
        return false;

    while (n > 1) {
        if (n % i == 0) {
            counts[i]++;
            n = n / i;
        } else {
            i++;
        }
    }

    int c = -1;

    for (std::map<int, int>::iterator iter = counts.begin(); iter != counts.end(); ++iter) {
        if (c == -1) {
            c = iter->second;
        } else {
            if (c != iter->second)
                return false;
        }
    }

    if (c > 1)
        return true;

    return false;
}

Take it the other way:

#include <stdio.h>

int main(void)
{
        int i, val, cnt, n = 26345 * 26345;

        for (i = 2; i * i <= n; i++) {
                val = i; 
                cnt = 1; 
                while (n != val && !(n % val)) {
                        cnt++;
                        val *= i; 
                }
                if (n == val) {
                        printf("%d=%d^%d\n", n, i, cnt);
                        break;
                }
        }
        return 0; 
}

public static boolean expression(int number){
		if(number==1){
			System.out.println("expression:1^1");
			return true;
		}
		ArrayList<Integer> arr = new ArrayList<Integer>();
		for(int i=2;i*i<=number;i++){
			if(number%i==0){
				arr.add(i);
			}
		}
		boolean canBeExpressed = false;
		for(int i=0;i<arr.size();i++){
			if(getPQExpression(arr.get(i),number)){
				canBeExpressed =true;
			}
		}
		return canBeExpressed;
	}
	private static boolean getPQExpression(int factor, int number) {
		int count = 0;
		while(number%factor==0){
			number = number/factor;
			count++;
		}
		if(number==1) {
			System.out.println("expression:"+factor +"^"+count);
			return true;
		}
		return false;
	}
	public static void main(String[] args) {
		expression(125);

	}

package temp2;
import java.util.Scanner;

public class praiseq {

public static void main(String[] args) {
double num,p=1,q=1;
Scanner s = new Scanner(System.in);
System.out.println("enter a value");
num = s.nextInt();
do{
p++;
q=1;
do{
q++;
System.out.println("" + p + q);
if(Math.pow(p,q) == num){
System.out.println(num + "is in the form of p^q");
System.exit(0);
}
}while(Math.pow(p,q) < num);

}while(Math.pow(p,2) <= num);

if(Math.pow(p,q) != num){
System.out.println(num + "is NOT in the form of p^q");
System.exit(0);
}
}

}

public static void main(String[] args) {
		int n = 250;
		findsol(n, 0);
	}

	private static int findsol(int num, int count) {

		for (int i = num; i > 0 && count < 2; i--) {
			if (Math.sqrt(i) % 1 != 0) {
				continue;
			} else {
				count++;
				int j = num - i;
				int result = 0;
				if (!(count >= 2) && j != 0)
					result = findsol(j, count);
				if (i + result == num && count < 3) {
					System.out.print((int) Math.sqrt(i) + " ");
					return i;
				}
				if (count >= 2)
					return 0;
				count = 0;
			}

		}
		return 0;
	}

int num1 = 1025;
		
		HashSet<Integer> primeFactors = new HashSet<Integer>();
		
		for(int i = 2; i< num1; i++) {
			int remainder = num1 % i;
			boolean aPrime = false;
			for(Integer j : primeFactors) {
				if(i % j == 0) {
					aPrime = true;
				}
			}
			
			if(remainder == 0 && !aPrime) {
				primeFactors.add(i);
			}
		}
		
		if(primeFactors.size() > 1) {
			System.out.println(num1+" cannot be represented as p^q");
		} else {
			System.out.println(num1+" can be represented as p^q");
		}

Check out this one simple solution..

#include <bits/stdc++.h>
#define ll long long
using namespace std;

bool solve(ll n) {
	
    int b;
    for(int a = 2; a <= sqrt(n); a++) {
    	b = 1;
        ll temp = pow(a,b);
        while(temp <= n && temp > 0) {
        	if(temp == n) {
                cout << a << " raised to the power of " << b << " = " << n << endl;
                return true;
            }
            else {
				b++;
				temp = pow(a,b);
			}
        }
             
	}
	
    return false; 
}
 
int main()
{   
 
 	int n;
 	cin >> n;
    if(!solve(n)) cout << "No" << endl;

	return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PerfectSquareNumber {
    
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Please enter an integer : ");
        int number = Integer.parseInt(reader.readLine());
        
        int sqrt = (int) Math.sqrt(number);
        if(sqrt*sqrt == number) {
            System.out.println(number+" is a perfect square number!");
        }else {
            System.out.println(number+" is NOT a perfect square number!");
        }
        
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PerfectSquareNumber {

public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Please enter an integer : ");
int number = Integer.parseInt(reader.readLine());

int sqrt = (int) Math.sqrt(number);
if(sqrt*sqrt == number) {
System.out.println(number+" is a perfect square number!");
}else {
System.out.println(number+" is NOT a perfect square number!");
}

}
}

how about using binary search solve this problem
will be O(logn)

A brute-force method in java. Can be improved with memoization et al, and most likely has overflow errors.

//
  //  Assumes that p and q are both > 1, so n must be >= 4.
  //
  public static boolean nCanBePToTheQ(long n) {
    if (n <= 4) {
      return true;
    }

    for (int p = 2; p < n; p++) {
      // trivial reject if n isn't a multiple of p
      if ((n % p) != 0) {
        continue;
      }

      for (int q = 2; q < n; q++ ) {
        long pToTheQ = (long) Math.pow(p, q);
        if (pToTheQ > n) {
          break;
        }

        if (pToTheQ == n) {
          System.out.printf("Woo-hoo! %d^%d == %d", p, q, n);
          return true;
        }
      }
    }

    return false;
  }

{{
#include <stdio.h>

int main(void) {
int num=4,temp=0,p=0,q=0;
int i,j;
for(i=2;i<=num/2;i++)
{
for(j=1;j<=num/2;j++)
{
if(pow(i,j)==num){temp=1;p=i;q=j;}
}
}
if(temp==1)
{
printf("no. found p=%d and q=%d",p,q);
}
return 0;
}
}}