Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Minimum number of weights

------------------------------------------------------------------------------------

• Choose a minimum number of weights to be able to measure all weights between 1-40 kg.

------------------------------------------------------------------------------------

Soln: To be able to measure 1 kg, one weight of 1 kg is a must.

To be able to measure 40 kg, sum of all weights chosen must be 40 kg.

We can choose 40 weights each of 1 kg.

This will enable us to measure all weights between 1 to 40 kg.

So, there at least is a solution - 40 weights each of 1 kg.

Optimization: Now, this can be optimised by binary method.

If we have one weight of 20 kg and 20 weights of 1 kg, we can still measure all values.

=> number of weights required is 1 + 20 = 21

The 20 weights of 1 kg are used both above and below 20 kg and their range can again be halved.

We can have 1 weight of 20 kg as before and 1 weight of 10 kg and 10 weights of 1 kg.

=> no. of weights required = 1 + 1 + 10 = 12

Half again the number of 1 kg weights

=> no. of weights required = 1 + 1 + 1 + 5 = 8

Again half

=> no. of weights required = 1 + 1 + 1 + 1 + 2 = 6

Thus, 6 weights are needed having weights 20, 10, 5, 3, 1, 1

Now, let us generalize the solution:

If weight range is 1-N, then weights required are:

N/2, N/4, N/8 ... 1, 1 (This last one weight helps to reach 2k from k)

=> Number of weights required are: logN + 1

Better Solution: The above solution does not take into account that the weights can be used as negative weights also. So, the weights need not be kept only on side of the balance, they can be kept on the other side of the balance too to increase the weight of the object.

1 kg weight is still a must.

To measure 2 kg, we can either have 2 kg or 1 kg +1 kg or 3 kg -1 kg weight combinations.

Off course, 3-1 is better, because we can then measure, 1, 2, 3 and 4 kg weights.

To measure 5 kg, we can do it as

5 or 1+4 or (3-1)+3 or 3+2 or 6-1 or 7-(3-1) or 8-3 or 9-(3+1)

Best is to choose last combo so we will get all weights from 1 to 13.

So to measure 1 to 13 kg weights, we need 1, 3, and 9 kg weights.

To measure 14, we need x-13=14 --> x=27 kg weight.

This seems to imply that a series of 1,3,9,27 ... 3^r can measure all

weights between 1 and 1+3+9+27...3^r = (3^r-1)/2

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: