the length of the rope is l units.

I can only cut any rope into two halves. for example if the length of the rope is 8 and we need a length of rope 6 we first cut into two halves and we get 4, 4 now we cut any of the half again and we get 4,2,2 now we can merge 4 and 2 and form a rope of length 6. in this example we need a minimum of 2 cuts to get the length of rope 6 from 8

assume that l is always a power of 2 and we need always a even length of rope from it how to find the number of minimum cuts needed to get the new rope?.

1st Solution

k -> rope of desired length.

l -> rope of given length

m = 2;

while(k%m==0 )

m *= 2;

ans :: (log2(l) - log2(m) + 1).

ex.

k = 6,l = 8

so initially m = 2;

after 1st iteration m = 4;

then break;

so min = log2(8) - log2(4) + 1 = 3 -2 + 1 = 2.

2nd Solution

for a number N

first set bit(From Left) is simply integer value of log(N)

last set bit can be calculated as

N = N-(N&(N-1)); and then Log(N)

int i = log(n);

n -= n&(n-1);

int j = log(n);

i-j will be the answer.

Refer here for more detail

## No comments:

Post a Comment