Least notes money exchange

Question

Suppose A and B are two good friends. A has borrowed \$n\$ dollar from B. Now B wants the money back from A and A is also ready to give it. But the problem is A has only \$x\$ dollar notes and B has \$y\$ dollar notes. They both want to keep the number of notes in exchange as low as possible.

As an example if \$n=37\$, \$x=5\$ and \$y=2\$, then the least amount of notes in exchange will be nine $5 notes from A and four $2 notes from B, which totals to $37.

Your input will be \$n, x, y\$ and your output should be the least of amount of notes possible for \$A\$ and \$B\$ such that \$B > 0\$. Input and output seperator can be anything, no leading zeros in input numbers, no negative numbers in input. Standard loopholes apply and shortest code wins.

Test Cases

37 5 2 -> 9 4
89 3 8 -> 35 2
100 12 7 -> 13 8
10 1 100 -> 110 1

Input will be always solvable.

Answer 1

J, 40 bytes

1 :'1+[:($#:u i.~,)[:+//(,-)*/1+[:i.u+]'

Try it online!

A bit labored as J code, but the idea is simple.

We construct a table with all the possible linear combinations, and just find the coordinates of what we're looking for:

In the actual code we drop the first column (because of the B > 0) constraint, and then have to add 1 to the returned coords, to adjust for 0-indexing.

Answer 2

Python 2, 51 bytes

n,x,y=input()
c=n+y
while c%x:c+=y
print(c-n)/y,c/x

Try it online!

-8 bytes thanks to Jonathan Allan

Answer 3

Brachylog, ¹⁴ 12 bytes

b;.z₂×ᵐ-~h?∧

Try it online!

The albeit strange constraint that the outputs must be ≥1 helps, as Brachylog tries only positive numbers for multiplication.

b;.z₂×ᵐ+~h?∧  [37,5,2]
b             [5,2]
 ;.           [[5,2], output]
   z₂         [[5, A], [2, B]]
     ×ᵐ       [5 * A, 2 * B]
       -      5 * A - 2 * B
        ~h?   [5 * A - 2 * B, X, Y] = [37, 5, 2]
           ∧  return the output [A,B] and solve the constraints

Answer 4

JavaScript (Node.js), 54 bytes

f=(n,x,y,i=0)=>(i-n)%y||n>i?f(n,x,y,i+x):[i/x,(i-n)/y]

Try it online!

Javascript beats Python!

Answer 5

JavaScript (V8), 45 bytes

x=>y=>n=>(g=m=>m%x?g(m+y):[m/x,(m-n)/y])(n+y)

Try it online!

Answer 6

Jelly,  14 13 12  11 bytes

-1 thanks to Nick Kennedy! (Dividing through and keeping those invariant under flooring is terser than testing divisibility and then integer dividing.)

‘r×ṀɗĖ÷ḞƑƇḢ

A dyadic Link accepting amount owed and a list of denominations [y, x] that yields a list of [B gives, A gives].

Try it online!

How?

‘r×ṀɗĖ÷ḞƑƇḢ - Link: integer, n; list of integers [y,x]
‘           - increment (n)
    ɗ       - last three links as a dyad - f(n+1,[y,x]):
   Ṁ        -   maximum ([y,x])
  ×         -   (n+1) multiplied by (that)
 r          -   inclusive range -> [n+1, n+2, ..., (n+1)×max([y,x])]
     Ė      -   enumerate -> [[1,n+1],[2,n+2],...]
                   (...note that this equals [[n+1-n,n+1],[n+2-n,n+2],...])
      ÷     -  divide by ([y,x])? (vectorises)
         Ƈ  - keep those which are:
        Ƒ   -   invariant under:
       Ḟ    -     floor
          Ḣ - head

Answer 7

JavaScript (V8), 41 39 bytes

(n,x,y)=>g=(B=1)=>(n+=y)%x?g(B+1):[n/x,B]  // 41 bytes, original

(n,x,y)=>g=B=>(n+=y)%x?g(-~B):[n/x,-~B]    // 39 bytes, user l4m2’s improvement

41 bytes, original

Try it online

The formula to satisfy is A * x = n + B * y, or A = (n + B * y) / x. Since we are looking for an A that is an integer, we try B = 1, 2, 3, … until n + B * y is divisible by x.

For B = 1, 2, 3, …, we have A * x = n + y, n + y + y, n + y + y + y, …, so we can reuse n to store A * x and increment it by y at the beginning of each iteration.

The solution is similar to Redwolf Programs’, and is equally 41 bytes long, but IMHO its form is different enough to merit being a separate answer, and the function accepts the arguments in a more natural form f(n,x,y) rather than f(n,x)(y).

39 bytes, user l4m2’s improvement

Try it online

~B gives the 2’s complement of B, which for non-negative integers is equivalent to -(B + 1). So -~B is equivalent to B+1… with the difference that ~B implicitly casts undefined to 0, so we no longer need to initialize B=0. What a trick! 🙌

Answer 8

Python 3, 50 bytes

f=lambda x,y,n,s=1:s+n%x and 1j+f(x,y,n+y,0)or n/x

Try it online!

Output as the format (9+4j)

Answer 9

Charcoal, 28 bytes

Ｎθ≔⁺×…·¹θＮＮη≔⌕﹪ηθ⁰ζＩ⟦÷§ηζθ⊕ζ

Try it online! Link is to verbose version of code. Takes input in the order x y n. Explanation:

Ｎθ

Input x.

≔⁺×…·¹θＮＮη

Form a range from 1 to x, multiply each element by y, and add n.

≔⌕﹪ηθ⁰ζ

Find the index of the first multiple of x, which is also 1 less than the number of notes for B.

Ｉ⟦÷§ηζθ⊕ζ

Calculate the number of notes for A and output the results on separate lines.

Answer 10

JavaScript (V8), 47 42 41 bytes

-5 from @Arnauld
-1 from @tsh

(n,x,b=0)=>g=y=>(++b,n+=y)%x?g(y):[n/x,b]

Try it online!

Old:

(n,x,b=0)=>g=y=>(a=++b*y+n)%x?g(y):[a/x,b]

Try it online!

Old:

(n,x,y)=>(g=b=>(a=b*y+n)/x%1?g(b+1):[a/x,b])(1)

Try it online!

Answer 11

APL (Dyalog Unicode), 21 20 bytes

Similar idea as Jonah's J answer, but quite a bit shorter due to APL's 1-indexing.

{⊃⍸⍺=⊃∘.-/⍵×⊂⍳⍺+⌈/⍵}

Try it online!

A dfn which takes n as left input ⍺ and the array x y as right argument ⍵:

             ⍳⍺+⌈/⍵   ⍝ indices from 1 to n + max(x, y)
          ⍵×⊂         ⍝ multiply x and y with each index
     ⊃∘.-/            ⍝ create a table of all pairwise differences
   ⍺=                 ⍝ for each value: does it equal n?
 ⊃⍸                   ⍝ get the first index of a 1

Answer 12

R, 54 50 bytes

function(n,x,y){while((m=n+T*y)%%x)T=T+1;c(m/x,T)}

Try it online!

Port of @hyper-neutrino's answer.

-4 bytes thanks to @Dominic

---

Port of @tsh's answer:

R, 53 bytes

f=function(n,x,y,s=1)"if"(s+n%%x,1i+f(n+y,x,y,0),n/x)

Try it online!

---

Other ports of @hyper-neutrino's answer:

R, 54 bytes

function(n,x,y,K=n+y){while(K%%x)K=K+y;c(K/x,(K-n)/y)}

Try it online!

R, 54 bytes

function(n,x,y,K=n){while((K=K+y)%%x)0;c(K/x,(K-n)/y)}

Try it online!

Answer 13

Haskell, 50 bytes

(x#y)n=[(div(n+i*y)x,i)|i<-[1..],mod(n+i*y)x<1]!!0

Try it online!

The relevant function is (#), which takes as input integers x, y, n and returns a pair (a,b), meaning that A should give a notes and B should give b back.

Answer 14

Java, 79 63 bytes

(n,x,y)->{int a=n/x,b;for(;(b=++a*x-n)%y>0;);return a+" "+b/y;}

Saved 16 bytes thanks to Olivier Grégoire.

Try it online!

Answer 15

C (clang), ⁶⁰ 58 bytes

Saved 2 bytes thanks to G. Sliepen!!!

f(n,x,y,s){(n+=y)%x?f(n,x,y,s+1):printf("%d %d",n/x,s+1);}

Try it online!

Uses the formula from Jonathan Allan's comment to hyper-neutrino's Python answer.

Answer 16

05AB1E, 22 bytes

∞*.Δ²@²y-³Ö*}D²α³÷,¹÷,

Try it online!

A port of hyper-neutrino's python answer.

Answer 17

Ruby, 38 bytes

->n,x,y{[1.step.find{(n+=y)%x<1},n/x]}

Try it online!

How

The trick is in 1.step.find: we add y to n at least once, and count iterations until n is divisible by x.

Outputs [B,A]

Answer 18

Lua, 75 bytes

load('n,x,y='.. .....' c=n repeat c=c+y until c%x==0 print(c/x,(c-n)/y)')()

Try it online!