# Need change of 78 cents [closed]

You bought a tasty Orange in the supermarket and got 78 cents change. How many possible ways the supermarket guy can give you the change using 1,5,10 or 25 coins

• Input: Change amount
• Output: The number of possible ways to give the change.

Order is not important 1,5 is same as 5,1

Win conditions:

1. Best performance
2. Shortest code

• wait, what, the task is to discard the input and output a constant? Commented Dec 13, 2013 at 9:14
• @JanDvorak is it more clear to you now? Commented Dec 13, 2013 at 9:21
• If the input is not guaranteed to be 78, perhaps you should specify that? So far, it's "output a precomputed constant" Commented Dec 13, 2013 at 9:22
• How are you planning to measure "best performance"? (Also, I've retagged from code-golf to code-challenge on the grounds that you're asking for a criterion other than length of code. Although code-challenge is a stretch too because it's a trivial problem). Commented Dec 13, 2013 at 9:30
• Your winning conditions are not very objective. Which is more important? Speed or chars? What about lengthy but speedy answers? What about short but not-so-fast answers? Commented Dec 13, 2013 at 18:25

# Mathematica answer= 121, chars=74 37

[121 ways to give change of $0.78, in pennies, nickels, dimes, and quarters.] Method 1: FroebeniusSolve This gives all the ways to solve the Frobenius equation p + 5n + 10d + 25q = c: FrobeniusSolve[{1, 5, 10, 25}, #]&  The number of ways is (37 chars): Length@FrobeniusSolve[{1,5,10,25},#]&  Examples Solutions are of the form, {pennies, nickels, dimes, quarters}:  FrobeniusSolve[{1, 5, 10, 25}, #]&[21]  {{1,0,2,0}, {1,2,1,0}, {1,4,0,0}, {6,1,1,0}, {6,3,0,0}, {11,0,1,0}, {11,2,0,0}, {16,1,0, 0}, {21,0,0,0}} Length@FrobeniusSolve[{1,5,10,25},#]&[78]  121 How many ways are there to give change to (.01 to$2.50)?

    Length@FrobeniusSolve[{1,5,10,25},#]&/@Range[250] // AbsoluteTiming


Timing: 2.004 sec

{2.00398, {{1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 2}, {6, 2}, {7, 2}, {8, 2}, {9, 2}, {10, 4}, {11, 4}, {12, 4}, {13, 4}, {14, 4}, {15, 6}, {16, 6}, {17, 6}, {18, 6}, {19, 6}, {20, 9}, {21, 9}, {22, 9}, {23, 9}, {24, 9}, {25, 13}, {26, 13}, {27, 13}, {28, 13}, {29, 13}, {30, 18}, {31, 18}, {32, 18}, {33, 18}, {34, 18}, {35, 24}, {36, 24}, {37, 24}, {38, 24}, {39, 24}, {40, 31}, {41, 31}, {42, 31}, {43, 31}, {44, 31}, {45, 39}, {46, 39}, {47, 39}, {48, 39}, {49, 39}, {50, 49}, {51, 49}, {52, 49}, {53, 49}, {54, 49}, {55, 60}, {56, 60}, {57, 60}, {58, 60}, {59, 60}, {60, 73}, {61, 73}, {62, 73}, {63, 73}, {64, 73}, {65, 87}, {66, 87}, {67, 87}, {68, 87}, {69, 87}, {70, 103}, {71, 103}, {72, 103}, {73, 103}, {74, 103}, {75, 121}, {76, 121}, {77, 121}, {78, 121}, {79, 121}, {80, 141}, {81, 141}, {82, 141}, {83, 141}, {84, 141}, {85, 163}, {86, 163}, {87, 163}, {88, 163}, {89, 163}, {90, 187}, {91, 187}, {92, 187}, {93, 187}, {94, 187}, {95, 213}, {96, 213}, {97, 213}, {98, 213}, {99, 213}, {100, 242}, {101, 242}, {102, 242}, {103, 242}, {104, 242}, {105, 273}, {106, 273}, {107, 273}, {108, 273}, {109, 273}, {110, 307}, {111, 307}, {112, 307}, {113, 307}, {114, 307}, {115, 343}, {116, 343}, {117, 343}, {118, 343}, {119, 343}, {120, 382}, {121, 382}, {122, 382}, {123, 382}, {124, 382}, {125, 424}, {126, 424}, {127, 424}, {128, 424}, {129, 424}, {130, 469}, {131, 469}, {132, 469}, {133, 469}, {134, 469}, {135, 517}, {136, 517}, {137, 517}, {138, 517}, {139, 517}, {140, 568}, {141, 568}, {142, 568}, {143, 568}, {144, 568}, {145, 622}, {146, 622}, {147, 622}, {148, 622}, {149, 622}, {150, 680}, {151, 680}, {152, 680}, {153, 680}, {154, 680}, {155, 741}, {156, 741}, {157, 741}, {158, 741}, {159, 741}, {160, 806}, {161, 806}, {162, 806}, {163, 806}, {164, 806}, {165, 874}, {166, 874}, {167, 874}, {168, 874}, {169, 874}, {170, 946}, {171, 946}, {172, 946}, {173, 946}, {174, 946}, {175, 1022}, {176, 1022}, {177, 1022}, {178, 1022}, {179, 1022}, {180, 1102}, {181, 1102}, {182, 1102}, {183, 1102}, {184, 1102}, {185, 1186}, {186, 1186}, {187, 1186}, {188, 1186}, {189, 1186}, {190, 1274}, {191, 1274}, {192, 1274}, {193, 1274}, {194, 1274}, {195, 1366}, {196, 1366}, {197, 1366}, {198, 1366}, {199, 1366}, {200, 1463}, {201, 1463}, {202, 1463}, {203, 1463}, {204, 1463}, {205, 1564}, {206, 1564}, {207, 1564}, {208, 1564}, {209, 1564}, {210, 1670}, {211, 1670}, {212, 1670}, {213, 1670}, {214, 1670}, {215, 1780}, {216, 1780}, {217, 1780}, {218, 1780}, {219, 1780}, {220, 1895}, {221, 1895}, {222, 1895}, {223, 1895}, {224, 1895}, {225, 2015}, {226, 2015}, {227, 2015}, {228, 2015}, {229, 2015}, {230, 2140}, {231, 2140}, {232, 2140}, {233, 2140}, {234, 2140}, {235, 2270}, {236, 2270}, {237, 2270}, {238, 2270}, {239, 2270}, {240, 2405}, {241, 2405}, {242, 2405}, {243, 2405}, {244, 2405}, {245, 2545}, {246, 2545}, {247, 2545}, {248, 2545}, {249, 2545}, {250, 2691}}}

Method 2: Solution by Solve (66 chars).

This solves the same equation listed in Method 1, albeit by a more standard method, Solve:

f[c_]:=Solve[p +5n+10d+25q==c &&p>=0&&n>= 0&&d>=0&&q>= 0,{p,n,d,q},Integers]


The number of ways is (74 chars):

g@c_:= Length@Solve[p +5n+10d+25q==c &&p>=0&&n>= 0&&d>=0&&q>= 0,{p,n,d,q},Integers]


Examples

 f[21]


{{p → 1, n → 0, d → 2, q → 0}, {p → 1, n → 2, d → 1, q → 0}, {p → 1, n → 4, d → 0, q → 0}, {p → 6, n → 1, d → 1, q → 0}, {p → 6, n → 3, d → 0, q → 0}, {p → 11, n → 0, d → 1, q → 0}, {p → 11, n → 2, d → 0, q → 0}, {p → 16, n → 1, d → 0, q → 0}, {p → 21, n → 0, d → 0, q → 0}}

 Length[f[78]]


121

How many ways are there to give change to (.01 to \$2.50)?

{#, g[#]} & /@ Range[250] // AbsoluteTiming


Timing: 4.72 sec

• Lots of space used on those constraints. Mathematica must have good support for generating functions: is that any shorter? Commented Dec 13, 2013 at 15:08
• There may be a shorter way to specify the set of non-negative integers, but I haven't found it. Anyway, I just found a distinct approach that only returns non-negative integers. Commented Dec 13, 2013 at 15:24

# K3 (kona), 121.

Simple dynamic progamming. 57 chars.

cg:{*{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]}

cg 78
121


Calculate all results up to 250 cents

  {{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]} 250
2691 2545 2545 2545 2545 2545 2405 2405 2405 2405 2405 2270 2270 2270 2270 2270 2140 2140 2140 2140 2140 2015 2015 2015 2015 2015 1895 1895 1895 1895 1895 1780 1780 1780 1780 1780 1670 1670 1670 1670 1670 1564 1564 1564 1564 1564 1463 1463 1463 1463 1463 1366 1366 1366 1366 1366 1274 1274 1274 1274 1274 1186 1186 1186 1186 1186 1102 1102 1102 1102 1102 1022 1022 1022 1022 1022 946 946 946 946 946 874 874 874 874 874 806 806 806 806 806 741 741 741 741 741 680 680 680 680 680 622 622 622 622 622 568 568 568 568 568 517 517 517 517 517 469 469 469 469 469 424 424 424 424 424 382 382 382 382 382 343 343 343 343 343 307 307 307 307 307 273 273 273 273 273 242 242 242 242 242 213 213 213 213 213 187 187 187 187 187 163 163 163 163 163 141 141 141 141 141 121 121 121 121 121 103 103 103 103 103 87 87 87 87 87 73 73 73 73 73 60 60 60 60 60 49 49 49 49 49 39 39 39 39 39 31 31 31 31 31 24 24 24 24 24 18 18 18 18 18 13 13 13 13 13 9 9 9 9 9 6 6 6 6 6 4 4 4 4 4 2 2 2 2 2 1 1 1 1 1


Time to do so (in milliseconds)

 \t {{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]} 250
10


Time to calculate up to 5000 cents: \t {{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]} 5000 360

result=121, javascript with memoize (160 chars)

c=[25,10,5,1]
d=[[1],[1],[1],[1]]
function f(x,y){
return d[x][y]||(d[x][y]=c.slice(x).reduce(function(i,j,k){
return i+(j>y?0:f(x+k,y-j))
},0))
}


result=121, javascript without memoize (126 chars)

c=[25,10,5,1]
function f(x,y){
return y?c.slice(x).reduce(function(i,j,k){
return i+(j>y?0:f(x+k,y-j))
},0):1
}


# J, 50 48 40

### result: 121

g=.{[:+//.@(*/)/0=1 5 10 25|"0 _ ]@i.@>:


Using generating functions approach. I'd say performance is not bad and can be easily made much better.

g 78
121
g 248
2545


Timing:

time'g 78'
0.000254s


## Haskell - 51 / 69

_%0=1;[]%_=0;(x:y)%m=sum[y%(m-i*x)|i<-[0..mdivx]]


Call notation: [1,5,10,25]%78

Or more complete with an extra line:

f=([1,5,10,25]%)


The call is just: f 78

Efficiency test (should be comparable with David Carraher):

main=mapM_(print.([1,5,10,25]%))[1..250]

> ghc -O2 frob.hs && time ./frob
- -
./frob  1.81s user 0.02s system 99% cpu 1.843 total