## abc Interview Question

Applications Developers**Country:**India

**Interview Type:**In-Person

Thank you.but how is the time complexity calculated here..? Can u plz help me with that

Sure, so think about what this algorithm is doing. We are constantly splitting the input in half. The time here is a question of how many times does it take us splitting the input in half to have 1 number remaining (aka 2^0 numbers remaining).

We start with an array of size size = n = 2^k.

Then we split the array in half, size = 2^(k-1)

Then again, size = 2^(k-2)

continue..

until size = 2^0 = 2^(k-k) = 1

It took us K steps to go from 2^K to 2^0. What is K in terms of N?

2^K = N, therefore, K = lg2(N)

since weigh balance is used we should consider splitting the group into 3 not 2 . 12 marbles should be split into three groups 4(g1) ,4(g2) , 4(g3) and weighed in the balance a below.

Assume g3 contains a heavier marble:

Case : (compare g1 and g2) If the g1 and g2 are weighed the balance will remain same so discard g1 , g2 and continue the same process with g3

Case where g1 is compared to g3 : weight balance will lean towards g3 heavier side so discard g1, g2 and and continue the same process with g3.

so Complexity becomes O(logN) where N is number of marbles and base of log is 3 not 2.

4

Divide the initial array into 3 piecesï¼šA B and C.

first: if A=B, then the odd one is in C.

C(a,b,c,d)

second if a=b,then: if a=c,the odd one is d

else the odd one is c

third if a!=b,then: if a=c, the odd one is b

else the odd one is a.

if A!=B

if A=C, the odd one is in B

else, the odd one is in A.

return the the steps 2nd and 3rd above.

so I think I need 4 steps to find the odd one.

Correct answer is 4

1. divide 12 marbles into group of 4.

2. now you have 3 groups - 4 marbles in each group. let;s call group A, B and C

3. Weigh group A vs B

case 1. A > B

4. Weigh A vs C

case 1.1 A > C - meaning group A has the defected marble. We also learned that defected marble in heavier.

5. Now divide group A' marble into group of 2 and weigh the two groups and so on until you find the defected marble. so far total attempts are 4

case 1.2 A == C - meaning group B has the defected marble and since A > B, defected marble in lighter. follow the above procedure. total attempts to discover defected marble in this case is 4

case 1.4 A < C - will it ever come here.. think about it

case 2. A < B

follow the above procedure

case 3 A== B - meaning C has the defected marble

pick 2 marbles from A and 2 from C. If they are equal then remaining 2 marbles will have the defected one. in that case pick 1 marble from A and 1 from remainining 2 from group C. weigh them if they are equal then last one is culprit.. if not equal then the current one is culprit.

so the correct answer is 4.

It asks for the minimum number. Look at your case 3, the number of times weighed is three (you just have to identify odd one out, not whether it is lighter or heavier). It would require some luck for this to occur, but it is the minimum number. I would give this as the response, and qualify it to say that 4 times would always result in an answer

1. divide 12 marbles into group of 4.

2. now you have 3 groups - 4 marbles in each group. let;s call group A, B and C

3. Weigh group A vs B

case 1. A > B

4. Weigh A vs C

case 1.1 A > C - meaning group A has the defected marble. We also learned that defected marble in heavier.

5. Now divide group A' marble into group of 2 and weigh the two groups and so on until you find the defected marble. so far total attempts are 4

case 1.2 A == C - meaning group B has the defected marble and since A > B, defected marble in lighter. follow the above procedure. total attempts to discover defected marble in this case is 4

case 1.4 A < C - will it ever come here.. think about it

case 2. A < B

follow the above procedure

case 3 A== B - meaning C has the defected marble

pick 2 marbles from A and 2 from C. If they are equal then remaining 2 marbles will have the defected one. in that case pick 1 marble from A and 1 from remainining 2 from group C. weigh them if they are equal then last one is culprit.. if not equal then the current one is culprit.

so the correct answer is 4.

2 < log_3(12) < 3, so at least 3 steps

btw, log_3(24) < 3, and we are able to find if the odd marble is heavier or lighter

1:

(1, 2, 3, 4) < (5, 6, 7, 8) => x in (1, 2, 3, 4) and lighter or x in (5, 6, 7, 8) and heavier

1.1:

(1, 2, 3, 5) < (4, 10, 11, 12) => x in (1, 2, 3) and lighter

1.1.1:

1 < 2 => 1 is odd marble and lighter

1.1.2:

1 > 2 => 2 is odd marble and lighter

1.1.3:

1 = 2 => 3 is odd marble and lighter

1.2:

(1, 2, 3, 5) > (4, 10, 11, 12) => x is 4 and lighter or x is 5 and heavier

1.2.1:

1 > 4 => 4 is odd and lighter

1.2.2:

1 = 4 => 5 is odd asd heavier

1.3:

(1, 2, 3, 5) = (4, 10, 11, 12) => x in (6, 7, 8) and heavier

1.3.1:

6 < 7 => 7 is odd and heavier

1.3.2:

6 > 7 => 6 is odd and heavier

1.3.3:

6 = 7 => 8 is odd and heavier

2:

(1, 2, 3, 4) > (5, 6, 7, 8) is simular as 1

3:

(1, 2, 3, 4) = (5, 6, 7, 8)

3.1:

(9, 10, 11) > (1, 2, 3) => x in (9, 10, 11) and heavier

3.1.1:

9 > 10 => 9 is odd and heavier

3.1.2:

9 < 10 => 10 is odd and heavier

3.1.3:

9 = 10 => 11 is odd and heavier

3.2:

(9, 10, 11) < (1, 2, 3) => x in (1, 2, 3) and lighter

3.2.1:

9 > 10 => 10 is odd and lighter

3.2.2:

9 < 10 => 9 is odd and lighter

3.2.3:

9 = 10 => 11 is odd and lighter

3.3:

(9, 10, 11) = (1, 2, 3) => 12 is odd

3.3.1:

12 < 1 => 12 is odd and lighter

3.3.2:

12 > 1 => 12 is odd and heavier

3 steps pf weighing required

1 .devide group of 12 stones to group of 6

2 .find the highest weighing group

3.devide the most weghted group to group of 3

4.find most weighted among these two groups having 3 stones

5.in that three stones weigh about any two stones if they are equal the third stone have higher weight. else stone in weigh scale have higher weight.

one correction :find it is higher or lower weight ,for that weigh between 6 vs 6 and

not position of each side.weigh 3 vs 3 on each find the group of equal weight.from this we can find unknown stone have high weight or less weight

3 try

Solution is little tricky (not a mathematical solution but a logical solution)---

Divide 12 balls in 3 sets of 4. Batch 1, Batch 2, Batch 3

1. Measure Batch 1 & Batch 2 (batch 1 on left side and batch 2 on right side)

2 a. left side goes up - If different ball is light then its in batch 1, if ball is heavy then its in batch 2. Take 3 balls from batch 1 and 2 ball from batch 2 place them on left side, take 4th ball from batch 1 and place it on right side along with 4 balls from batch 3.

3 a. Left side still goes down - Ball is light and its one of the 3 balls that are placed on left side. take two of them and measure. lighter one will be different if they weight same then 3rd ball is different

3 b. Right side goes down - Either two balls placed on left side from batch 2 are heavy or 4th ball placed on right side from batch 1 is light. Measure the 2 balls from batch 2. If they are same then its the 4th ball from batch 1 which is light, if t they are not same then take the heavy one. That's different

3 c. If both side remains same then different ball is in 2 balls left from batch 2 and its heavy. Measure them and take the heavy one

2 b. Left side goes down - then the above logic will still hold true

2 c. Both side weight same - Different ball is in batch 3. Take 3 balls from batch 3 and 3 balls from batch 1 and weight them.

3 a . Batch 1 balls goes down then it means ball is heavy and its one of the 3 balls from batch 3. Take two balls from batch 3 and measure and take the heavy one. If they weight same take 3rd ball

3 b. Batch 1 goes - same logic hold true

3 c. Both batches weight same - Its the 4th ball from batch 3 which is different. Measure it against any other ball to find if its heavy or light

3 try

Solution is little tricky (not a mathematical solution but a logical solution)---

Divide 12 balls in 3 sets of 4. Batch 1, Batch 2, Batch 3

1. Measure Batch 1 & Batch 2 (batch 1 on left side and batch 2 on right side)

2 a. left side goes up - If different ball is light then its in batch 1, if ball is heavy then its in batch 2. Take 3 balls from batch 1 and 2 ball from batch 2 place them on left side, take 4th ball from batch 1 and place it on right side along with 4 balls from batch 3.

3 a. Left side still goes down - Ball is light and its one of the 3 balls that are placed on left side. take two of them and measure. lighter one will be different if they weight same then 3rd ball is different

3 b. Right side goes down - Either two balls placed on left side from batch 2 are heavy or 4th ball placed on right side from batch 1 is light. Measure the 2 balls from batch 2. If they are same then its the 4th ball from batch 1 which is light, if t they are not same then take the heavy one. That's different

3 c. If both side remains same then different ball is in 2 balls left from batch 2 and its heavy. Measure them and take the heavy one

2 b. Left side goes down - then the above logic will still hold true

2 c. Both side weight same - Different ball is in batch 3. Take 3 balls from batch 3 and 3 balls from batch 1 and weight them.

3 a . Batch 1 balls goes down then it means ball is heavy and its one of the 3 balls from batch 3. Take two balls from batch 3 and measure and take the heavy one. If they weight same take 3rd ball

3 b. Batch 1 goes - same logic hold true

3 c. Both batches weight same - Its the 4th ball from batch 3 which is different. Measure it against any other ball to find if its heavy or light

I didn't use a algorithm or standard written logic. I sort of did this the way that Dalip did it. However, I was not aware of the question not allowing 1 marble being weighed.

I would weigh 2 marbles individually. That would give me the possibility of 2 of the same weights. For instance/example, 2oz but if I were to get two of the same results that would mean that the majority of the marbles were that weight because only 1 is heavier or lighter.

I would then multiply 2oz by the 11 = 22oz. I would then weigh the whole group of marbles after performing this math. If I measured 23oz then the one marble is 1oz lighter than the other marbles. If I measured 25oz then the marble is 1 oz heavier than than the other marbles.

This is probably wrong and I missed something in my logic but it made sense to me at the time.

3 tries.

Divide 12 balls in 3 sets of 4. say A, B, C

weight A against B, if both are equal, then defected marble is in C otherwise if A > B defected marble is in B(weigh count 1)

suppose B has defected ball:

take 3 marble from each B and A or C, if both has same weight that means 4th ball from B is defected.(weigh count 2)

if weight of 3 balls from B are not equal to A balls, then weight any two ball from B if weight are different then we found defected ball otherwise 3rd ball is defected.(weigh count 3)

suppose C has defected ball:

take 3 marble from each C and A or B, if both has same weight that means 4th ball from C is defected.(weigh count 2)

if weight of 3 balls from C are not equal to A balls, then weight any two ball from C if weight are different then we found defected ball otherwise 3rd ball is defected.(weigh count 3)

i don't know why people are saying 4 , the correct ans is ""3"":

1. at first divide the 12 marbles into 3 pieces of 4.

2. put 4 pieces one side and 4 on other side of the weight scale,

case 1: the wieghts are equal:

1.1 it means the lighter one is from the 4 not in weight scale.

from that 4 marbles,put 2 marbles on both side of the scale

1.2 the one which is lighter has the light marble

1.3 put the one marble on each scale, and you'll get the lightest marble.

case 2: the weights are not equal:

strt from 1.2

Divide the initial array into 4 pieces. One side will have 2 equal parts and the other side will have 2 non-equal parts. Use the equal side to tell the weight of the normal marble. Now binary search the unequal side of the array by splitting the current portion in half and moving to the half that's weight doesn't logically make sense given the normal marble weight. Once you have a single marble selected, that should be the odd one out.

- jbaum517 August 07, 2015This is an O(lgn) time algorithm and O(1) space.