The price you cannot pay

Problem

In the harbor market of Tyre, nobody gives change: you pay the exact amount or you leave with nothing. A merchant checks his purse before going in and wants to know the smallest price he could not pay.

Write a function that takes coins, a list with the value of each coin (positive integers; it may be empty or have repeated values), and returns an integer: the smallest price, from 1 up, that no combination of the coins pays exactly. Each coin is used at most once.

With 1, 2 and 5 you can pay 1, 2 and 3 (1 + 2), but not 4: the answer is 4. With an empty purse you cannot even pay 1, so you return 1.

A hint: look at the coins from smallest to largest. If the ones you have seen so far already pay any price from 1 to s, think about which new prices the next one opens up, and when it leaves a gap.

Examples

• The example

  [1, 2, 5] → 4

• Only 1s

  [1, 1, 1, 1] → 5

• No coin of 1

  [2, 3] → 1

• A gap after several coins

  [1, 1, 3, 7] → 6

• Out of order

  [4, 1, 2] → 8

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def unpayable(coins):
    pass

function unpayable(coins) {
}