Saturday, May 10, 2014

Get the job puzzle

Problem

A company plan to recruit people. But, ends up finding many more than eligible people.So, they plan a strategy to cut short the people to their suit the headcount of their requirement.
People will be lined up in a queue 1, 2, 3… N.  At first phase, people at odd locations will be eliminated. Same thing will apply for next phase.
For example,
Round 1: 1, 2, 3, 4, 5, 6….N
Round 2:  2, 4, 6.. N  (People at odd locations eliminated)
Round 3: 4, 6… N (People at odd locations eliminated)

Given the value of N, where will you position yourself to take up the job ??


Solution


I would choose position is the last power of 2 within N for example, if N=17, the last power of 2 is 16 (2^4)
To be more specific,We have to chose the position of 2 raised to the power of x, where x is the no. of eliminations required to reduce n number of people to a final one.
x can be calculated by using a simple while loop.
x=0;
while(N>1)
{
    N=N/2;
    x=x+1;
}

Reference

0 comments:

Post a Comment