20
\$\begingroup\$

Suppose we have two different types of coin which are worth relatively prime positive integer amounts. In this case, it is possible to make change for all but finitely many quantities. Your job is to find the largest amount that cannot be made with these two types of coin.

Task

Input: A pair of relatively prime integers \$(a,b)\$ such that \$1<a<b\$.

Output: The largest integer that cannot be expressed as \$ax+by\$ where \$x\$ and \$y\$ are nonnegative integers.

Scoring:

This is code golf so shortest answer in bytes wins.

Example:

Input \$(3,11)\$

\$4\cdot 3- 1\cdot 11=1\$, so if \$n\geq 22\$ we can write \$n=q\cdot 3 + 2\cdot 11 +r\$ where \$q\$ is the quotient and \$r\in\{0,1,2\}\$ the remainder after dividing \$n-22\$ by \$3\$. The combination \$(q+4r)\cdot 3 + (2-r)\cdot 11 = n\$ is a nonnegative combination equal to \$n\$. Thus the answer is less than \$22\$. We can make \$21=7\cdot 3\$ and \$20=3\cdot 3 + 1\cdot 11\$ but it's impossible to make \$19\$ so the output should be \$19\$.

Test Cases:

[ 2,  3] => 1

[ 2,  7] => 5

[ 3,  7] => 11

[ 3, 11] => 19

[ 5,  8] => 27

[ 7, 12] => 65

[19, 23] => 395

[19, 27] => 467

[29, 39] => 1063

[ 1,  7] => error / undefined behavior (inputs not greater than one)

[ 6, 15] => error / undefined behavior (not relatively prime).

[ 3,  2] => error / undefined behavior (3 > 2)

[-3,  7] => error / undefined behavior (-3 < 0)
\$\endgroup\$
8
  • 2
    \$\begingroup\$ I remember seeing this challenge before, but I'm not coming up with it on searching. \$\endgroup\$
    – xnor
    Jan 11, 2020 at 3:13
  • \$\begingroup\$ @xnor I thought there was a good chance it would be a duplicate but I also failed to find it when I searched. \$\endgroup\$
    – Hood
    Jan 11, 2020 at 3:39
  • 2
    \$\begingroup\$ There is a problem for any number of coins. But I don't think it is a duplicate, because most answers here do not work for the case with more than 2 coins. \$\endgroup\$
    – alephalpha
    Jan 11, 2020 at 4:26
  • 2
    \$\begingroup\$ Here's a proof for the formula by one of the diamond mods of Math.SE. \$\endgroup\$ Jan 12, 2020 at 15:11
  • 2
    \$\begingroup\$ @Jonah I am not. I am a mathematician (I study algebra, specifically homotopy theory) and hobbyist programmer. \$\endgroup\$
    – Hood
    Jan 12, 2020 at 18:30

21 Answers 21

15
\$\begingroup\$

J, 7,6 3 bytes

-1 byte thanks to FrownyFrog !

-3 bytes thanks to Grimmy!

*-+

Try it online!

     -    subtract
      +   the sum of the arguments
    *     from their product
\$\endgroup\$
8
  • 2
    \$\begingroup\$ 3 bytes with *-+ \$\endgroup\$
    – Grimmy
    Jan 11, 2020 at 11:10
  • \$\begingroup\$ @Grimmy Great - this is much better! Thanks! \$\endgroup\$ Jan 11, 2020 at 11:57
  • 2
    \$\begingroup\$ Seeing answers like this in J make me glad to lurk. \$\endgroup\$
    – cole
    Jan 12, 2020 at 20:38
  • 2
    \$\begingroup\$ fails on the "not relative prime"-Example 6 f 15 which results in 69 \$\endgroup\$
    – eagle275
    Jan 13, 2020 at 14:12
  • 1
    \$\begingroup\$ @@eagle275 it is undefined behavior, as stated in the OP \$\endgroup\$ Jan 13, 2020 at 14:50
10
\$\begingroup\$

Husk, 4 bytes

←¤*←

Try it online!

Explanation

As proved in lots of places, the answer for inputs a and b is ab-a-b = (a-1)(b-1)-1. ¤ is the 'combine' combinator, so ¤*← is a function that applies (decrement) to each argument and 'combines' the results by multiplication. Then I decrement the result to get the final output.

\$\endgroup\$
9
\$\begingroup\$

Wolfram Language (Mathematica), 8 bytes

1##-+##&

Try it online!


Wolfram Language (Mathematica), 15 bytes

FrobeniusNumber

Try it online!

\$\endgroup\$
3
  • 9
    \$\begingroup\$ Because of course there's a builtin for that. \$\endgroup\$ Jan 11, 2020 at 10:36
  • 6
    \$\begingroup\$ Is there a language that just has all the Mathematica builtins but as single characters? \$\endgroup\$
    – Sam Dean
    Jan 13, 2020 at 9:04
  • \$\begingroup\$ @SamDeann How would that be possible, assuming that the number of builtins is more than the number of characters? \$\endgroup\$ Jan 14, 2020 at 6:39
7
\$\begingroup\$

05AB1E, 3 bytes

<P<

Try it online!

<         # decrement both inputs
 P        # product
  <       # decrement
\$\endgroup\$
4
\$\begingroup\$

Python 3, 18 bytes

lambda a,b:a*b-a-b

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Perl 6, 43 13 bytes

(*-1)*(*-1)-1

Try it online!

Turns out there's a much shorter way to calculate the answer.

Perl 6, 43 bytes

->\a,\b{max ^(a*b)∖((a X*^b)X+(^a X*b)):}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog Unicode), 3 bytes

×-+

Try it online!

Dyadic train where a f b computes (a×b)-(a+b).

Jelly, 3 bytes

×_+

Try it online!

Dyadic link that takes two numbers a and b as left and right arguments. Works the same as the APL version, just with the symbol _ instead of - to represent subtraction.

\$\endgroup\$
3
\$\begingroup\$

C (clang), 31 22 bytes

f(a,b){return~-a*b-a;}

Try it online!

Saved 9 bytes thanks to ceilingcat!!!

\$\endgroup\$
0
3
\$\begingroup\$

Jelly, 3 bytes

P_S

Try it online!

A monadic link taking a pair of integers. Same method as most other answers (product minus sum).

\$\endgroup\$
3
\$\begingroup\$

Pyth, 5 bytes

-*FQs

Try it online!

Product minus sum.

t*FtM

Try it online!

a,b -> (a-1)*(b-1)-1

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 18 bytes

f(a,b){a=~-a*b-a;}

Noodle9's answer except using a= instead of return.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Java 8, 13 bytes

a->b->a*b-a-b

Try it online.

Explanation:

Similar as most other answers, it calculate the product minus the sum:

a->b->         // Method with two integer parameters and integer return-type
      a*b      //  Return the two parameters multiplied by each other,
         -a-b  //  after we've also subtracted both parameters from this product
\$\endgroup\$
2
\$\begingroup\$

Whitespace, 59 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][S N
S _Duplicate_input][S N
S _Duplicate_input][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][S N
S _Duplicate_input][S T S S T   S N
_Copy_0-based_2nd][T    S S N
_Multiply_top_two][S N
T   _Swap_top_two][T    S S T   _Subtract_top_two][S N
T   _Swap_top_two][T    S S T   _Subtract_top_two][T    N
S T _Print_as_integer_to_STDOUT]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer a = STDIN as integer
Integer b = STDIN as integer
Integer c = a * b
c = c - a - b
Print c as integer to STDOUT

Not much golfing involved, except for using the first input as heap-address for the second input, since it's guaranteed to be positive and we push it to stack right away.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 8 7 bytes

t*thQte

Try it online!

Uses the formula (a-1)(b-1) - 1. Takes input as a Python array of 2 integers.

-1 by using implicit appended Q

\$\endgroup\$
2
  • \$\begingroup\$ @FryAmTheEggman: isaacg already posted that as a separate solution, so I don't think it's worth editing this one, given how it's a rather different approach. \$\endgroup\$ Jan 13, 2020 at 17:58
  • \$\begingroup\$ Ah, didn't see that, sorry! \$\endgroup\$ Jan 13, 2020 at 19:04
1
\$\begingroup\$

Japt, 4 bytes

×-Ux

Try it here

\$\endgroup\$
1
\$\begingroup\$

Keg, 5 bytes

*¿¿+-

Simply a port of other answers. Uses latest github interpreter.

\$\endgroup\$
1
\$\begingroup\$

Excel, 12 bytes

=A1*B1-A1-B1

Same approach as other answers.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (V8), 13 bytes

a=>b=>a*b-a-b

Try it online!

Same solution as other answers, I almost didn't post it but for once I found a question without a JS answer, so may as well. In fact this is the exact same as Kevin Cruijssen's answer, replacing Java's lambda -> with Javascript's =>. I've included a very basic testing framework in my TIO link so it does all the test cases. Most invalid inputs still execute.

\$\endgroup\$
1
\$\begingroup\$

Brainf*ck, 36 bytes

Cell layout: cells 1 and 2 are input, cell 3 is where the final answer is built, cell 4 is auxiliary

,->,-<[->[->+>+<<]>>[-<<+>>]<<<]>>-.

Or, with words:

,-               read a and decrement
>                move to cell 2
,-               read b and decrement
<                move back to a
 [-              while a isn't 0, decrement once and
  >              move to b (to add b to cells 3 and 4)
  [-             decrement b
   >+>+<<        add 1 to cells 3 and 4, go back to b
  ]
  >>             move to cell 4
  [-<<+>>]       copy cell 4 to cell 2 (i.e. put b again in cell 2
 <<<             move back to a
 ]
>>-.             go to cell 3, decrement and output

Try it online - this is not a link to tio.run. In this site I linked I was able to give input as \02\05 so that I could try smaller test cases, and I also get a "memory dump" to check the weird characters that were printed actually correspond to the answer.

Here, have a tio.run link as well.

\$\endgroup\$
1
\$\begingroup\$

AWK, 14 bytes

$0=$1*$2-$1-$2

Try it online!

Assumes input in the form of x y.

\$\endgroup\$
0
\$\begingroup\$

R, 11 7 bytes

a*b-a-b

Where a and b are the 2 numbers.

Thanks to Jo King for pointing out my error.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Is this actually taking input, or is a a predefined variable (which is not allowed)? \$\endgroup\$
    – Jo King
    Jan 12, 2020 at 23:06
  • \$\begingroup\$ Ah good point @JoKing. I sometimes get confused with how to input the values on CG. Changed! \$\endgroup\$
    – sam
    Jan 19, 2020 at 20:05
  • \$\begingroup\$ ...I don't think this is any better is it? Now you're using two predefined variables? It should be prefixed with function(a,b) or something like that \$\endgroup\$
    – Jo King
    Jan 19, 2020 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.