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\$ 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\$ 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\$ 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\$ 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\$ 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\$ 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\$
    – user100690
    May 8 at 7:05
  • \$\begingroup\$ And 50 bytes: tio.run/##y0osSyxOLsosKNHNy09J/… if function is unnamed \$\endgroup\$
    – user100690
    May 8 at 7:07
  • \$\begingroup\$ @JonathanAllan Nice optimization! \$\endgroup\$
    – emanresu A
    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\$ 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\$ 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\$
    – emanresu A
    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\$
    – emanresu A
    May 8 at 3:06
  • \$\begingroup\$ @Ausername Good point (also @hyper-neutrino). I'd been recursing with f previously :p \$\endgroup\$ 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\$ 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\$ 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\$ May 8 at 21:17
  • \$\begingroup\$ 61 bytes by rethinking the entire algorithm (that's really different from what you wrote) \$\endgroup\$ 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.