Statistics

Problem Statement for "GreedyChange"

Problem Statement

Many monetary systems have the nice property that, when giving change, a greedy algorithm will always produce the fewest number of coins possible. In other words, if you are trying to produce a certain amount of change, then something like the following algorithm will produce the fewest coins possible:

number of coins = 0;
while(amount>0){
	find the largest coin, c, that is less than or equal to amount;
	subtract the value of c from amount and increment the number of coins;
}

For example, the American monetary system with coins valued at 1, 5, 10, and 25 cents has this property. However, it is not difficult to construct values of coins that do not have this property. If the values of your coins are 1, 3 and 4, then you can make 6 with two 3's. The algorithm above, on the other hand, will use 3 coins - a 4 and two 1's.

Your task is to write a class GreedyChange, with a method smallest that takes a int[], denominations, representing the values of the various coins in some monetary system. You should return the smallest amount of money for which the greedy algorithm does not produce the fewest coins possible. If the greedy algorithm always produces the fewest coins possible, return -1. To guarantee that the greedy algorithm always works (terminates), there will always be a coin worth 1.

Definition

Class:
GreedyChange
Method:
smallest
Parameters:
int[]
Returns:
int
Method signature:
int smallest(int[] denominations)
(be sure your method is public)

Constraints

  • denominations will contain between 1 and 50 elements, inclusive.
  • Each element of denominations will be between 1 and 500,000, inclusive.
  • At least one of the elements of denominations will be 1.

Examples

  1. {1,25,10,5}

    Returns: -1

    In this system, the greedy algorithm always produces an optimal result.

  2. {1,3,4}

    Returns: 6

    If we need to make 6, the greedy algorithm does so as 4 + 1 + 1. However, the optimal solution is 3 + 3.

  3. {1,10,10,20,25}

    Returns: 30

    Note that elements may be repeated.

  4. {1,15,25}

    Returns: 30

  5. {1,3,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,500000}

    Returns: 98

  6. {1,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50, 52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,500000}

    Returns: -1

  7. {500000, 499999, 499998, 499997, 499996, 499995, 499994, 499993, 499992, 499991, 499990, 499989, 499988, 499987, 499986, 499985, 499984, 499983, 499982, 499981, 499980, 499979, 499978, 499977, 499976, 499975, 499974, 499973, 499972, 499971, 499970, 499969, 499968, 499967, 499966, 499965, 499964, 499963, 499962, 499961, 499960, 499959, 499958, 499957, 499956, 499955, 499954, 499953, 499952, 1}

    Returns: 999904

  8. {500000,499999,1}

    Returns: 999998

  9. {500000,499999,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 999998

  10. {1,367731,145236,376034,392659,447682,436259,404021,138718,447804,268597}

    Returns: 277436

  11. {1,174423,268282,312179,401751,339165,325949,158458,155492,98040,181845,230145,425516,236636,332320,51416,497929,21296,63679,321681,451341,306305,300100,113413,91707,360871,232536,345120,138575,183443,202281,464223,321255,268659,327088,11433,159166}

    Returns: 22866

  12. {1,199979,428151,394446,489868,161325,111476,316891,89766,143287,317619,71400,115819,412378,63806,466294,32885,190697,181240,307256}

    Returns: 65770

  13. {1,119283,127192,366103,447790,338088,73058}

    Returns: 146116

  14. {1,285413,96208,146976,226900,48286,273319,24564,208862,175739,488655,329417,337786,420758,97418,26152,160822,88790,326150,163162,281835,195375,78402,449635,333696,104568}

    Returns: 49128

  15. {1,231979,375083,454748,228729}

    Returns: 457458

  16. {1,96854,126163,119202,287896,88824,155438,122414,157418,361579,356273,424326,78898,339981,462703,492806,77961,145068,371522,360696,50293,159313,23871,277054,281675,126535,132488,41578,163926,372226,330738,398277,287634,142673,392315,253588,204345,51953,446368,201450,215824,194746,91808,383243,66091,129873,496705}

    Returns: 47742

  17. {1,383095,164570,453898,168148,141228,172725,452366,487264}

    Returns: 282456

  18. {1,61656,115369,251297,51268,461488,351026,39439,78342,248771,258741,142034,92627,131703,235766,266670,71508,218200,332191,312165,389755,259978,209793,412667,320180,115953,70411,280759,375075,406467}

    Returns: 78878

  19. {1,33236,469103,336194,154291,166133,339876,248071,110132,156622,71138,133164,472313,308551}

    Returns: 99708

  20. {1,62142,47834,425690,7035,322846,71557,192149,47585,445433,177832,262973,320891,271657,11198,19596,376621,278091,74773,224579,402924,494419,456392,418018,112104,67425,317240,334000,76211,308876,475439,379683,426289,431242,67947,311817,269026,119033,128118,165986,67559,105502,473426}

    Returns: 14070

  21. {1,79423,24571,58072,28228,243930,486057,408599,343126,163699,78606,427152,223716,30640,339252,216608,128583,5383,141066,154598,430698,170945,441139,219312,383365}

    Returns: 26915

  22. {1,399937,48945,290650,264283,30078,398840,486881,386968,257659,45560,431421,460940,82487,275574,254750,286122,404925,387683,449767,407350,46514,132977,88279,19083}

    Returns: 38166

  23. {1,213875,456782}

    Returns: 641625

  24. {1,293383,364630,347968,273532,229938,139758,414732,120345,171191,343897,492066,91184,338590,46938,118826,435058,170922,341581,146178,386377,464311,417006,302427,397127,339433,141986,394962,298316,213982,173494,469227}

    Returns: 93876

  25. {1,199189,132757,211903,58596,157998,119705,180886,292656,59506,268899,68207,180668,239368,185267,153674,159763,229069,436359,386813,402863,448348,319343,142608,316740,264495,365576,132541,441640,209871,493360,216624,494369,14699,370360,454400,236670,56040,401152,153270,243804,345832,312530}

    Returns: 58796

  26. {1,494430,280958,69423,306465,2200,56563,317670,15544,461915,400145,216402,425822,88678,118457,392402,180022,487135,361824,321584,31055,499757,1227,218579,326964,48016,82331,494467,69984,498394,467623,24772,357415,56365,2919,355141,213660,115776,347715,60451,352566,368528,490217}

    Returns: 2454

  27. {1,267120,310003,427346,323248,229578,59379,27618,368028,299283,150799,210521,314692,277684,141291,269855,37803,220515,24403,440484,224810,115593,34726,158029,431041,161374,477764}

    Returns: 48806

  28. {1,70980,236198,222079,417363,497634,131035,446192,50469,441429,429614,141417,384941,402833,58945,233609,495009,118766,558,1773,239694,451886,448180,239524,274672,483944,321084,326597,331915,229670,494063,51894,383154,226033,384693,157049,434545,293206,146525}

    Returns: 2232

  29. {1,409412,8208,152834,471739,363517,379958,219742,86434,143060,365326,109805,4578,39410,219800}

    Returns: 9156

  30. {1,142514,16602,233500,67079,267362,187685,163533,148220,75954,394241,137046,383062,208747,499767,465863,46908,205255,342044,183202,389304,66246,202242,185714,409631,199753,139233,140009}

    Returns: 49806

  31. {1,92888,106418,291767,166948,69540,415352,497740,120039,465183,335550,186129,311065,474388,423091,39272,294885,304033,51954,484010,234813,95802,81526,69794,264525,365228,131304,12299,446018,441372,49533,81226,466289,81172,356372,114941,385791,75533,214163,251770,250269,260472,327462,477990}

    Returns: 49196

  32. {1,395891,103717,305948,399130,377038,411829,312243,472112,199258,360308,385543,182494,5333,179322,356334,431946,406527,31666,206826,361918}

    Returns: 31998

  33. {1,396537,288186,17125,440526,66947,404455,187476,310357}

    Returns: 68500

  34. {1,257710,492480,376009,26330,87446,51969,109890,307796,378641,194868,105906,139139,257594,93772,216542,105464,142397,477288,392974,470289,365748,164331,66294,364172,341864,85023,301010}

    Returns: 52660

  35. {1,406324,201340,298165,102678,217984,317344,124738}

    Returns: 205356

  36. {1,75441,173595,298434,26814,167045,453273,62529,461066,143089,388550,344142,456587,471558,44939,1094,237269,314691,78600}

    Returns: 27350

  37. {1,389909,142619}

    Returns: 427857

  38. {1,406279,477452,482481,307082,267886,400223,86642,455869,439117,50898,392067,360035,342956,190282,434349,476590,41267,430442,374574,414718,495696,249356,494916,422009,358987,76932,419764,400915,298876,186130}

    Returns: 82534

  39. {1,471619,499775,394878,490519,96025,83649,434554,312685,104280,240829,269071,104077,119970,363904,154910,52781,363097,433454,316926,330413,120927,313018,277379,412132,316009,472568,116321,483154,67903,474647,260348,437066,440605,325438,293695,403425,191166,14197,260734,377320,286675,238798}

    Returns: 56788

  40. {1,362006,236553,442615,38606,477190,395024,368473,284491,230196,324659,369146,43335,94967,76049,200669,447,194784,330942,464679,253581,238528,276615,259056,3720,417495,327739,442353,468339,229992,388721,216788,277738,164328,254219,487033,371348,337332,478497,157601,245423,55151,105292,190311,316101,335814,39024,355135,152545}

    Returns: 4023

  41. {1,55482,172680,403739,87176,495512,64608,389462,185241,58781,199502,51081,349426,316341,445997,261014,246618,90507,222432,371069,155152}

    Returns: 102162

  42. {1,362857,339332,93551,322165,402914,312882,221233,809,425918,159327,346087,145354,299423,133996,477846,443845,275613,141628,173300,85703}

    Returns: 93793

  43. {1,401440,429655}

    Returns: 802880

  44. {1,222659,252736,95714,272874,307141,344530,187072,58715,490849,37147,111128,257650,5498,6341,130491,312448,431182,281234,419223,92096,270974,266173,295369,301286,201481,193625,145349}

    Returns: 10996

  45. {1,150927,430292,191059,200436,30639,111868,88871,300514,73268,213205,391275,196664,311623,370127,146478,385209,265716,56725,359090,101347,392392}

    Returns: 61278

  46. {1,185843,149260,291909,359113,94352,208071,58856,263064}

    Returns: 117712

  47. {1,433070,11006,311541,316399,248272,329030,183364,257928,131169,392416,164154,19990,423449,302510,283863,431479,262469,242310,368998,367310,117466,434419,217371,424448,131734,23544,172064}

    Returns: 22012

  48. {1}

    Returns: -1

  49. {1,227967}

    Returns: -1

  50. {1,353767}

    Returns: -1

  51. {1,75629,351740,11855,496784,464754,370916,178464,292952,166413,425906,336779,238796}

    Returns: 82985

  52. {1,117279,436693,49285,432081,274965,153737,204507,10635,263426,136236,340058,387148,253057,257736,173100,133973,369760,198863,385052,311053,484731}

    Returns: 53175

  53. {1,208557,210156,334711,483959,121158,443030,169337,458820,30976,278455,206641,41781,150807,41861,340406,253801,396109,253009,283762}

    Returns: 61952

  54. {1,109738,492174,152281,348314,211620,253314,386798,86227,495127,263928,391263,296116,243583,425604,314185,4957,120083,156707,33547,324192,391744,499229,114556,330911,485544,385484,297202,363315,137039,447205,436284,182591,485565,189479,260467,307277,389916}

    Returns: 34699

  55. {1,338845,383373,487040,270769,243629,213677,92951,347085,75776,33220,449842,494273,276741,284162,56281,124239,483980,13169,378433,405763,100462,87003,129380,132684}

    Returns: 39507

  56. {1,197976,20930,249544,272265,109903,437676,207237,362095,277311,356653,292428,75290,355933,37537,498804,485678,210894,38180,385667,52108,320469,468139,199958}

    Returns: 41860

  57. {1,467971}

    Returns: -1

  58. {1,321462,110658,312039,303728,327797,456034,326500}

    Returns: 331974

  59. {1,165701,274622,204963,434800,58221,250969,132461,392733,373571,275508,336673,431701,230783,207596,44668,317296,119669,308699,387609,469177}

    Returns: 89336

  60. {500000,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    Returns: -1

  61. { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144 }

    Returns: -1

  62. { 1, 1, 1, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 80, 84, 86, 88, 90, 92, 94, 96, 500000 }

    Returns: 82

  63. { 1, 2, 3 }

    Returns: -1

  64. { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000 }

    Returns: -1

  65. { 250, 100, 1 }

    Returns: 300

  66. { 1, 3, 4, 5 }

    Returns: 7

  67. { 1, 50, 110 }

    Returns: 150

  68. { 500000, 499999, 1 }

    Returns: 999998

  69. { 1, 25010, 50000, 25020, 10, 20, 30, 40 }

    Returns: -1

  70. { 1, 2 }

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: