The two-pan balance
- O(2ⁿ) · Legendary
- Full plan
- Python
- JavaScript
- recursion
- lists
- operations
Problem
Lucía Ferrer, a chemist, weighs her powders on a two-pan balance with a handful of weights. She puts the powder on one pan, and each weight can go on the other pan, on the same pan as the powder, or stay off. When the balance is level, she knows how much the powder weighs. She wants to know how many different amounts she can measure this way.
Write a function that takes weights, a list of positive whole numbers (it may be empty or have repeated values). Return a whole number: how many different positive whole amounts can be measured. Each weight is used at most once: on the opposite pan, on the powder's pan, or on neither.
With [1, 3] she measures 1 and 3 with a single weight, 4 with both together, and 2 by putting the 3 on the opposite pan and the 1 next to the powder, because 3 = 2 + 1. Return 4. With [2, 5] she measures 2, 5, 7 and 3: also 4.
Examples
The example
[1, 3] → 4
Two weights that aren't consecutive
[2, 5] → 4
From 1 to 13 with no gaps
[1, 3, 9] → 13
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def measurable(weights):
passJavaScript
function measurable(weights) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.