## IIT-D Interview Question

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

i think its ans comes out to be.......if k >= ceil value of(log n ) at base 3 ...it'll always be possible.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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";

}``````

Comment hidden because of low score. Click to expand.
0

numItems / 2? What if numItems is odd?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``k >= ceil[ log(n/2) ] where log to base 2``

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.