Amazon Interview Question
SDE1sCountry: United States
Interview Type: Written Test
your solution will not work for 125 (example): this number not perfect square but represent as 5 power 3.
my solution to check p power q presentation is (this solution checking any power is available. also trick to minimize the operation is i*i <= n):
static bool IsPowerPresented(int n)
{
if (n == 0)
throw new Exception("wrong input");
if (n == 1)
return true;
if (n == 2)
return true;
int temp = n;
for(int i=2; i*i <= n; i++)
{
temp = n;
while(temp > 1)
{
if (temp % i != 0)
break;
temp = temp / i;
}
if (temp == 1)
return true;
}
return false;
}
when i = 5, it will see that log(125)/log(5) = 3 which is an integer
what do you mean it doesn't work?
For me (C#) : Value of : Log(125)/Log(5) is coming as :
temp = 3.0000000000000004
and Ceiling value (4) not equal to temp.
After some changes it works perfectly. This is how I got correct answer after improving your code. Btw, your logic is awesome!
static boolean isPerfectPower(double n) {
for (double i = 2; i*i < n; i++) {
double temp = Math.log(n)/Math.log(i);
System.out.println(temp);
System.out.println(Math.round(temp));
if (Math.abs(Math.round(temp) - temp)<0.00000000000001) { 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
Given p != 1 and q != 1, the solution is
<?php
function div($der, $dee, &$cache) {
$key = $der . ',' . $dee;
if (!isset($cache[$key])) {
if ($der % $dee == 0) {
if ($der == $dee) {
$cache[$key] = true;
} else {
$cache[$key] = div($der / $dee, $dee, $cache);
}
} else {
$cache[$key] = false;
}
}
return $cache[$key];
}
function isPower($n, &$cache) {
if (!isset($cache[$n])) {
$res = false;
for ($i = 2; $i < $n; $i++) {
if (isPower($i, $cache)) {
continue;
}
if (div($n, $i, $cache)) {
$res = true;
break;
}
}
$cache[$n] = $res;
}
return $cache[$n];
}
$cache = [];
for ($n = 2; $n < 1000; $n++) {
print $n . ": " . (isPower($n, $cache) ? "true" : "false") . "\n";
}
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
}
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;
}
}
Sorry, I was trying to find with for loop was better so used random function and run the code a million time.
Please replace the line for fetching random number by
N = sc.nextInt();
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;
}
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 minCount = INT_MAX;
for (std::map<int, int>::iterator iter = counts.begin(); iter != counts.end(); ++iter) {
if (iter->second > 0 && iter->second < minCount)
minCount = iter->second;
}
if (minCount < 2 || minCount == INT_MAX)
return false;
for (std::map<int, int>::iterator iter = counts.begin(); iter != counts.end(); ++iter) {
if (iter->second % minCount)
return false;
}
return true;
}
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!");
}
}
}
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;
}
Perfect powers in linear time?
- Skor February 06, 2015