Amazon Interview Question
Software Engineer / DevelopersCountry: United States
The complexity of this algorithm is actually O(n). The depth of the call tree is log n, but the total number of multiplication remains (n-1).
I don't know why we are even talking about O(logN), if both the numbers are 4 byte integers, logN cannot be greater than 31. Working on that, here is the O(1) version of the algorithm. pow(a,b) where b is the power a has to be raised to. If b is taken to be s1s2u1u2s3...sN, where s indicates a set bit and u indicates an unset bit, then pow(a,b) will be equal to a^(2^s1)*a^(2^s2)*a^(2^s3)....a^(2^sN) where s1, s2..sN are the positions of the set bits of b.
The corresponding code (in java) is:
public static String pow(int a, int b)
{
int lsb= 0x1;
BigInteger result= new BigInteger("1");
BigInteger exponent= new BigInteger(""+a);
while(b>=lsb)
{
if((b&lsb)>0)
result= result.multiply(exponent);
lsb= lsb<<1;
exponent= exponent.multiply(exponent);
}
return result.toString();
}
I don't know why we are even talking about O(logN), if both the numbers are 4 byte integers, logN cannot be greater than 31. Working on that, here is the O(1) version of the algorithm. pow(a,b) where b is the power a has to be raised to. If b is taken to be s1s2u1u2s3...sN, where s indicates a set bit and u indicates an unset bit, then pow(a,b) will be equal to a^(2^s1)*a^(2^s2)*a^(2^s3)....a^(2^sN) where s1, s2..sN are the positions of the set bits of b.
The corresponding code (in java) is:
public static String pow(int a, int b)
{
int lsb= 0x1;
BigInteger result= new BigInteger("1");
BigInteger exponent= new BigInteger(""+a);
while(b>=lsb)
{
if((b&lsb)>0)
result= result.multiply(exponent);
lsb= lsb<<1;
exponent= exponent.multiply(exponent);
}
return result.toString();
}
- Abhishek March 23, 2012