IIT-D Interview Question
Country: India
Interview Type: In-Person
void CheckPossibilities( int numItems, int maxWeights )
{
if( numItems <= 0 )
{
cout << "Invalid Items";
return;
}
if ( maxWeights <= 0 )
{
cout << "Impossible";
return;
}
if ( numItems <= 2 )
{
cout << "Possible";
return;
}
int reminder = 0;
while( maxWeights > 0 )
{
numItems = numItems / 2;
maxWeights--;
}
if( numItems <= 1 )
cout << "Possible";
else
cout << "Impossible";
}
This is based on divide and conquer approach. If N is even put N/2 coins on both side of the weight balance. One having less weight has the fake coin. Again do the same on N/2 coins until you get 1 coin on each side. One having less weight will be the fake coin.
If N is odd or in some intermediate step of above algo (when N is even and N/2 is odd) , We cannot divide in 2 parts so remove one coin from the N coins now N-1 will be even, divide it and weight it ,if both has same weight then the removed coin is fake coin if not then the (N-1)/2 coins having less weight will have fake coin. Repeat the process until you get fake coin.
i think its ans comes out to be.......if k >= ceil value of(log n ) at base 3 ...it'll always be possible.
- naive June 14, 2013