## Amazon Interview Question

- 0of 0 votes
A calculator with only ":=" and "x". Given a and n, find the smallest number of multiplications to compute b=a^n

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