# Least notes money exchange

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. • Are all inputs guaranteed to be positive integers? Does B always use notes (should 10, 1, 100 give 10, 0 or 110, 1?) May 8 at 3:00 • Please update the question. Especially for "Everyone use notes" two of the three answers so far do not do that, and it's not obvious. May 8 at 3:07 • ...although I don't see why the friends would bother doing 110, 1 when they could do 10, 0! May 8 at 3:08 • That really doesn't make sense. May 8 at 4:24 • Needing B to give back at least one note strikes me as a needless gotcha. – xnor May 8 at 7:44 ## 18 Answers # 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.

# 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

• 69 bytes. Nice. May 8 at 2:50
• Save 8 like this May 8 at 6:21
• @JonathanAllan Ah, that's smart. Thanks! May 8 at 6:43

# Brachylog, 14 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


# 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!

• my 2 preferred languages all gone... and I'm bad enough that I can't out golf u guys May 8 at 3:01
• Since I golfed 8 off the Python answer, I'll put JavaScript back in front with the same change TIO :) May 8 at 6:37
• 52 bytes: tio.run/##y0osSyxOLsosKNHNy09J/f8/… at the cost of calling f(37,5,2)() instead of f(37,5,2)
– user100690
May 8 at 7:05
• And 50 bytes: tio.run/##y0osSyxOLsosKNHNy09J/… if function is unnamed
– user100690
May 8 at 7:07
• @JonathanAllan Nice optimization! May 8 at 8:31

# JavaScript (V8), 45 bytes

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


Try it online!

• change your name to "tsh the outgolfer" :P May 8 at 6:43
• Ah, a curried version of what I commented a few mins earlier (TIO). I don't know JS syntax well enough for that! May 8 at 6:50

# 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)
Ṁ        -   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

• Nie golf @NickKennedy, thanks! May 8 at 20:18

# 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! 🙌

• 39
– l4m2
May 10 at 22:21
• Nice trick @l4m2, I updated the answer. Thanks. May 11 at 14:35

# 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)

# 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.

# JavaScript (V8), 4742 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!

• I'm sad now. 47 because outer function doesn't need to be named. May 8 at 3:05
• Do you need to name f? Also imagine being able to do two lambdas without spending like 20 bytes on lambda ...: May 8 at 3:05
• @hyper-neutrino ninja'd May 8 at 3:06
• @Ausername Good point (also @hyper-neutrino). I'd been recursing with f previously :p May 8 at 3:08
• Also, I'm not sure why you're doing /x%1. So, 42 bytes, I guess? May 8 at 8:32

# 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


# R, 54 50 bytes

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


Try it online!

-4 bytes thanks to @Dominic

### 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!

### 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!

• 50 bytes by getting rid of the repeated (n+T*y) expression in the last one... May 9 at 15:37

(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.

# 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!

• 73 bytes by using b (which you somehow kept while it was useless) to store store a*x-n. May 8 at 21:09
• 63 bytes by switching output type from int[] to String, and merging the +1 and the a++ to a prefixing ++a. May 8 at 21:17
• 61 bytes by rethinking the entire algorithm (that's really different from what you wrote) May 8 at 21:58

# C (clang), 60 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.

• A recursive version in 58 bytes: f(n,x,y,s){(n+=y)%x?f(n,x,y,s+1):printf("%d %d",n/x,s+1);} Basically a port of @dwardu's answer. May 9 at 9:57
• @G.Sliepen Good idea but the problem with recursion like that is it's dependent on $s$ picking up its $0$ initialisation from the stack, which may or may not be $0$. May 9 at 17:54
• Undefined behavior is perfectly acceptable for Code Golf. If it runs on tio.run, it is fine ;) May 9 at 18:50
• @G.Sliepen True, don't know why I think like that golfing - thanks! :D May 9 at 20:58

# 05AB1E, 22 bytes

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


Try it online!

A port of hyper-neutrino's python answer.

• 15 bytes with input as y, n, x. (Some savings are probably from Jonathan Allan's golf)
– ovs
May 8 at 11:53

# 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]

# 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!