8
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Are all inputs guaranteed to be positive integers? Does B always use notes (should 10, 1, 100 give 10, 0 or 110, 1?) \$\endgroup\$ – Jonathan Allan May 8 at 3:00
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Allan May 8 at 3:07
  • 11
    \$\begingroup\$ ...although I don't see why the friends would bother doing 110, 1 when they could do 10, 0! \$\endgroup\$ – Jonathan Allan May 8 at 3:08
  • 3
    \$\begingroup\$ That really doesn't make sense. \$\endgroup\$ – Jonah May 8 at 4:24
  • 13
    \$\begingroup\$ Needing B to give back at least one note strikes me as a needless gotcha. \$\endgroup\$ – xnor May 8 at 7:44

18 Answers 18

7
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
3
  • 5
    \$\begingroup\$ 69 bytes. Nice. \$\endgroup\$ – lyxal May 8 at 2:50
  • 1
    \$\begingroup\$ Save 8 like this \$\endgroup\$ – Jonathan Allan May 8 at 6:21
  • \$\begingroup\$ @JonathanAllan Ah, that's smart. Thanks! \$\endgroup\$ – hyper-neutrino May 8 at 6:43
7
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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!

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

JavaScript (V8), 45 bytes

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

Try it online!

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

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nie golf @NickKennedy, thanks! \$\endgroup\$ – Jonathan Allan May 8 at 20:18
4
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 39 \$\endgroup\$ – l4m2 May 10 at 22:21
  • \$\begingroup\$ Nice trick @l4m2, I updated the answer. Thanks. \$\endgroup\$ – dwardu May 11 at 14:35
3
\$\begingroup\$

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)

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

Charcoal, 28 bytes

Nθ≔⁺×…·¹θNNη≔⌕﹪ηθ⁰ζI⟦÷§ηζθ⊕ζ

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

Nθ

Input x.

≔⁺×…·¹θNNη

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.

I⟦÷§ηζθ⊕ζ

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

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

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!

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

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 50 bytes by getting rid of the repeated (n+T*y) expression in the last one... \$\endgroup\$ – Dominic van Essen May 9 at 15:37
2
\$\begingroup\$

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.

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

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!

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

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ – G. Sliepen May 9 at 9:57
  • \$\begingroup\$ @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\$. \$\endgroup\$ – Noodle9 May 9 at 17:54
  • \$\begingroup\$ Undefined behavior is perfectly acceptable for Code Golf. If it runs on tio.run, it is fine ;) \$\endgroup\$ – G. Sliepen May 9 at 18:50
  • \$\begingroup\$ @G.Sliepen True, don't know why I think like that golfing - thanks! :D \$\endgroup\$ – Noodle9 May 9 at 20:58
1
\$\begingroup\$

05AB1E, 22 bytes

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

Try it online!

A port of hyper-neutrino's python answer.

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

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]

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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