The official currency of the imaginary nation of Golfenistan is the foo, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos. One can see that it's not possible to pay certain amounts, like 4 foos, using these coins. Nevertheless, all large enough amounts can be formed. Your job is to find the largest amount that can't be formed with the coins (5 foos in this case), which is known as the coin problem.
Your input is a list
L = [n1, n2, ..., nk] of positive integers, representing the values of coins in circulation.
Two things are guaranteed about it:
- The GCD of the elements of
Ldoes not contain the number 1.
It may be unsorted and/or contain duplicates (think special edition coins).
Since the GCD of
L is 1, every large enough integer
m can be expressed as a non-negative linear combination of its elements; in other words, we have
m = a1*n1 + a2*n2 + ... + ak*nk
for some integers
ai ≥ 0.
Your output is the largest integer that cannot be expressed in this form.
As a hint, it is known that the output is always less than
(n1 - 1)*(nk - 1), if
nk are the maximal and minimal elements of
You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. If your language has a built-in operation for this, you may not use it. There are no requirements for time or memory efficiency, except that you should be able to evaluate the test cases before posting your answer.
After I posted this challenge, user @vihan pointed out that Stack Overflow has an exact duplicate. Based on this Meta discussion, this challenge will not be deleted as a duplicate; however, I ask that all answers based on those of the SO version should cite the originals, be given the Community Wiki status, and be deleted if the original author wishes to post their answer here.
[3, 7, 8] -> 5 [25, 10, 16] -> 79 [11, 12, 13, 14, 13, 14] -> 43 [101, 10] -> 899 [101, 10, 899] -> 889 [101, 10, 11] -> 89 [30, 105, 70, 42] -> 383 [2, 51, 6] -> 49