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
