Adobe Interview Question
Computer ScientistsIn the above solution, the complexity will be linear. Slight modification below to make it logarithmic
int pow(int x, int n)
{
if(n==0)return(1);
else if(n%2==0)
{
int tmp = pow(x,n/2);
return tmp*tmp;
}
else
{
return(x*pow(x,n-1));
}
}
You are ryt about your implementation. But the question is something else.
I think the correct answer is 27.
#include<stdio.h>
#include<conio.h>
int count;
int pow(int x, int n)
{
if(n==0)return(1);
else if(n%2==0)
{
count++;
return(pow(x,n/2)*pow(x,(n/2)));
}
else
{
count+=2;
return(x*pow(x,n/2)*pow(x,(n/2)));
}
}
int main()
{
count = 0;
pow(5,12);
printf("\nMultiplication Count : %d", count);
getch();
return 0;
}
Run to see the answer..:)
below is the java code which gives the count as 11 and which is correct 27 is really foolish.
public static void main(String[] args)
{
new TestMethods().pow(5, 12);
System.out.println("\nMultiplication Count :"+ count);
}
private static int count=0;
public int pow(int x, int n)
{
if(n==0)return(1);
else if(n==1) return x;
else if(n%2==0)
{
count++;
System.out.println("\nMultiplication Count even:"+ count+" "+x+" "+n);
return(pow(x,n/2)*pow(x,(n/2)));
}
else
{
count+=2;
System.out.println("\nMultiplication Count :odd"+ count+" "+x+" "+n);
return(x*pow(x,n/2)*pow(x,(n/2)));
}
}
if you have common mathametic sence you can undersatnd that 5^12 or pow(5,12) sould have exactly 11 multiplications
Original code:
5^12 = 5^6 * 5^6
5^6 = 5^3 * 5^3
5^3 = 5 * 5^2
5^2 = 5^1 * 5^1
5^1 = 5 * 5^0
5 multiplication
unsigned int power(unsigned int x, unsigned int y)
{
unsigned int prod = 1, temp = x;
assert(x || y);
if (x < 2) return x;
for (; y; y = y >> 1)
{
if (y & 1) prod *= temp;
temp = temp * temp;
}
return prod;
}
here has no more than 2 * floor(log2(y)) multiplication. In the case, y = 12, it needs 6
sorry 5 for this one. The original use much more:
int pow(int x, int n)
{
if(n==0)return(1);
else if(n%2==0)
{
int tmp = pow(x,n/2);
return tmp*tmp;
}
else
{
return(x*pow(x,n-1));
}
}
Orignal Code:
1 + 2 * ( 1 + 2 * ( 2 + 2 * (2)))
Every time it recursive call, the number of underlining multiplicatoin duplicate.
i think ans is 27....
- srirupesh@gmail.com July 25, 2011(5,12)
=(5,6)*(5,6)
=(5,3)*(5,3)*(5,3)*(5,3)
={5*(5,1)*(5,1)}*{5*(5,1)*(5,1)}*{5*(5,1)*(5,1)}*{5*(5,1)*(5,1)}
=[5*{(5*(5,0)*(5,0))*(5*(5,0)*(5,0))}]*[5*{(5*(5,0)*(5,0))*(5*(5,0)*(5,0))}]*[5*{(5*(5,0)*(5,0))*(5*(5,0)*(5,0))}]*[5*{(5*(5,0)*(5,0))*(5*(5,0)*(5,0))}]
@Sandeep think 10 times before saying anybody as FOOL :P