Minimum number of weights - PrismoSkills

Minimum number of weights - PrismoSkills

• 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.

Read full article from Minimum number of weights - PrismoSkills