What strategy should be used to kill the fewest dwarfs, and what is the minimum number of dwarfs that can be saved with this strategy?

A dwarf-killing giant lines up 10 dwarfs from shortest to tallest. Each dwarf can see all the shortest dwarfs in front of him, but cannot see the dwarfs behind himself. The giant randomly puts a white or black hat on each dwarf. No dwarf can see their own hat. The giant tells all the dwarfs that he will ask each dwarf, starting with the tallest, for the color of his hat. If the dwarf answers incorrectly, the giant will kill the dwarf. Each dwarf can hear the previous answers, but cannot hear when a dwarf is killed. What strategy should be used to kill the fewest dwarfs, and what is the minimum number of dwarfs that can be saved with this strategy?

Source: http://www.businessinsider.com/toughest-job-interview-questions-2013-7?op=1#ixzz2a9upxPNJ

Minimum Number of Cuts Needed to Cut Rope in get the rope of desired length

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