Minimum number of weights - PrismoSkills
To be able to measure 40 kg, sum of all weights chosen must be 40 kg.
- 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.
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
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
Read full article from Minimum number of weights - PrismoSkills