You are given N number of weights that are all powers of 2. You are also given an item that weighs 1003 lbs.
(1) Exactly how many of those weights would be needed to balance the weight of the item if you could only use one of each weight?
(2) What's the fewest number of weights you can use to balance the weight of the item if there is an unlimited amount of each weight available to you?
|
|
Submitted by luvya
|
|
Rating: 2.3333 (6 votes)
|
|
|
Solution:
|
(Hide)
|
(1)You would need exactly 8 weights.
If you add up these weights:
1 lb, 2 lbs, 4, 8, 16, 32, 64, 128, 256, and 512,
the sum is 1023. The difference between 1003 and 1023 is 20, so you must discard the only 2 weights that add up 20, and they are 16 and 4.
Now you know the only weights you need are:
1 lb, 2 lbs, 8, 32, 64, 128, 256, & 512.
(2)The whole point of this second question is to prove that only way to make a number using the least amount of powers of two is to simply do it the binary-related way. The answer to this second question is the same as (1). |
