Need change of 78 cents 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:


Best performance 
Shortest code


Also please add the result for 78 in your title.
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}, #]&amp;


The number of ways is (37 chars):

Length@FrobeniusSolve[{1,5,10,25},#]&amp;


Examples

Solutions are of the form, {pennies, nickels, dimes, quarters}:

 FrobeniusSolve[{1, 5, 10, 25}, #]&amp;[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},#]&amp;[78]



  121




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

    Length@FrobeniusSolve[{1,5,10,25},#]&amp;/@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 &amp;&amp;p&gt;=0&amp;&amp;n&gt;= 0&amp;&amp;d&gt;=0&amp;&amp;q&gt;= 0,{p,n,d,q},Integers]


The number of ways is (74 chars):

g@c_:= Length@Solve[p +5n+10d+25q==c &amp;&amp;p&gt;=0&amp;&amp;n&gt;= 0&amp;&amp;d&gt;=0&amp;&amp;q&gt;= 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[#]} &amp; /@ Range[250] // AbsoluteTiming


Timing: 4.72 sec