Amazon Interview Question
if we have to calculate 2^10 , instead of multiplying 10 times, we just calculate pow(4,5) and so on. Copied the below code from somewhere, hope it helps
function power_for_quicker( value, power ) {
var result = 1;
while ( power != 0 ) {
if ( power & 1 == 0 ) {
value = value * value;
power = power / 2;
} else {
result = result * value;
power = power - 1;
}
}
return result;
}
The smallest number of multiplications should be log(n).
suppose you have aaaaaaaaaaaaaa....... First calculate axa, which is the 1st multiplication, then you do axa x axa, which used the 2nd multiplication, then axaxaxa x axaxaxa which is 3rd multiplication, keep going. It takes log_2 (n) multiplications.
1. first compute N1 and N2 defined as:
N1 = floor(log2(n))
N2 = n - 2 ** N1
2. the number of multiplications needed is,
m = N1 + (# of bits set to 1 in N2)
(example)
the following is the example when n = 14:
N1 = floor(log2(14)) = 3
N2 = n - 2 ** N1 = 14 - 8 = 6
m = 3 + 2 = 5
a ** 14 is computed as follows using 5 multiplications.
a2 = a * a
a4 = a2 * a2
a8 = a4 * a4
a12 = a8 * a4
a14 = a12 * a2
2*LOG(N) IN WORST Case
A^n = a^N/2 *A^N/2 (N EVEN)
A^N = A^N/2* A^N/2*A (N IS ODD)
1) t(N) = T(N/2) +1 FOR EVEN
2) T(N) = T(N/2) +2 FOR ODD
for worst case we need to consider the 2nd case.
assuming number is power is like somwthing like 2^n -1 then after divison
power will always be odd.
so, t(n) = 2 + t(n/2)
t(n/2) = 2+ t(n/4)
t(n/4) = 2+ t(n/8)
t(n)= 2+ 2 +2 +..
--------------------
(log(n) steps)
t(n) = 2log(n)
logN
- Anonymous April 01, 2010