Statistics

Problem Statement for "Collector"

Problem Statement

Victor travels around the world collecting coins. He is now in Surria and he would like to obtain at least one of each kind of Surrian coin. He is at a cash machine, and he only has time to make a single withdrawal before he has to leave. It is unknown how the machine determines which coins to return, so Victor must withdraw an amount that guarantees his goal.

You are given a int[] coins containing the values of each kind of Surrian coin. Note that multiple kinds of coins might actually have the same value, in which case, he still needs to get one of each kind (see example 3). Return the minimal sum that Victor must withdraw from the cash machine to receive at least one of each kind, or -1 if it is impossible. Assume that the machine carries an infinite supply of each kind of coin.

Definition

Class:
Collector
Method:
minimalSum
Parameters:
int[]
Returns:
int
Method signature:
int minimalSum(int[] coins)
(be sure your method is public)

Constraints

  • coins will contain between 1 and 50 elements, inclusive.
  • Each element of coins will be between 1 and 10000, inclusive.

Examples

  1. {1,2}

    Returns: -1

    It is impossible to guarantee that he will receive a "2" coin. Any sum can be achieved using only "1" coins.

  2. {1}

    Returns: 1

  3. {8255,9548}

    Returns: 17803

  4. {9793,7287}

    Returns: 17080

  5. {4105,2325}

    Returns: 6430

  6. {1677,32}

    Returns: 1709

  7. {5389,1414}

    Returns: 6803

  8. {7060,116,4042}

    Returns: 11218

  9. {7644,1077,7215}

    Returns: 15936

  10. {1932,3308,4678}

    Returns: 9918

  11. {7604,2702,8828}

    Returns: 19134

  12. {6516,7810,7178}

    Returns: 21504

  13. {4497,7943,7941,5503}

    Returns: 25884

  14. {2307,2705,7929,9438}

    Returns: 22379

  15. {3229,1636,746,1521}

    Returns: 7132

  16. {9889,3005,566,3367}

    Returns: 16827

  17. {1560,6705,420,5840}

    Returns: 14525

  18. {9831,2722,7982,2994,9853}

    Returns: 33382

  19. {5502,74,9782,7881,7524}

    Returns: 30763

  20. {8612,3084,7761,9031,6583}

    Returns: 35071

  21. {1656,9429,4981,3605,4919}

    Returns: 24590

  22. {6322,4922,8922,5613,9185}

    Returns: 34964

  23. {1918,6304,6902,4730,1068,1644}

    Returns: 22566

  24. {874,4734,8027,1717,5490,2691}

    Returns: 23533

  25. {3387,6476,7124,1565,9258,7452}

    Returns: 35262

  26. {9273,1350,4166,2800,5840,5690}

    Returns: 29119

  27. {1037,1391,5718,4203,7243,7886}

    Returns: 27478

  28. {9261,6704,1411,5817,6459,4698,6405}

    Returns: 40755

  29. {5621,2086,9554,5213,9434,6262,6158}

    Returns: 44328

  30. {2662,9785,3421,8631,5271,8608,9937}

    Returns: 48315

  31. {4596,6556,9465,4747,8003,2362,5055}

    Returns: 40784

  32. {6203,5662,5335,1506,1585,6911,2101}

    Returns: 29303

  33. {5781,5744,8980,5092,5396,6938,1674,4260}

    Returns: 43865

  34. {6613,4452,5687,7576,4330,4981,1899,7700}

    Returns: 43238

  35. {6501,8942,7025,8572,7780,8550,6375,3141}

    Returns: 56886

  36. {4363,7779,3283,9413,7247,9060,4125,3712}

    Returns: 48982

  37. {7968,2744,5602,4234,5922,7064,2817,7836}

    Returns: 44187

  38. {4287,8147,9560,3261,9021,5813,5408,7326,4366}

    Returns: 57189

  39. {8945,4472,9717,5932,9189,9995,6081,8220,5544}

    Returns: 68095

  40. {9164,6976,8816,8688,9496,4767,6454,9090,9122}

    Returns: 72573

  41. {7409,5020,6408,5027,4949,9075,3861,5572,8954}

    Returns: 56275

  42. {4165,5685,7477,8221,9130,9901,5115,9726,5853}

    Returns: 65273

  43. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: -1

  44. {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}

    Returns: -1

  45. {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    Returns: -1

  46. {1,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    Returns: -1

  47. {1956,9013}

    Returns: 10969

  48. {5517,463,5281,9586,8636}

    Returns: 29483

  49. {2540,2103,6573,2893,890,639,45,9320}

    Returns: -1

  50. {9023,7667,3305,2556,2775,3716,9630,3529,8000,1173,1741}

    Returns: -1

  51. {1174,5276,5006,1051,3724,3763,7291,1663,5401,4334,250,1511,7710,3373}

    Returns: -1

  52. {5696,4467,8449,3265,7317,3432,6092,7955,6707,4014,8860,411,4603,643,3251,6874,4705}

    Returns: -1

  53. {1190,4310,5009,6539,6285,3408,2615,9861,5951,4413,1319,4368,4714,7264,688,6670,4271,2317,1043,9639}

    Returns: -1

  54. {353,3792,4872,7240,3770,1348,7002,4687,6325,8253,5750,2464,5509,6543,8704,2963,2989,6004,3998,8148,2198,6698,5899}

    Returns: -1

  55. {4929,9532,6050,6149,5168,9041,8802,2255,4246,5768,9252,656,1265,8363,5237,6146,3151,6070,119,5477,7364,9578,3936,809,5320,9771}

    Returns: -1

  56. {4952,551,4903,4434,7535,1609,8607,9948,3828,4253,9446,8313,9311,3174,3937,3758,2264,6122,6062,1011,5614,5909,1947,2918,4898,3317,4956,1862,6201}

    Returns: -1

  57. {9421,9178,5176,6269,2146,3070,2038,7420,6513,1754,9067,1175,1254,3360,7912,2740,134,5225,1922,6141,2087,111,5553,6751,5234,1331,7331,9452,2696,6329,3783,4810}

    Returns: -1

  58. {7162,2055,5043,2322,5136,2762,2751,6977,2387,1856,1815,2314,8002,7935,2653,1442,4817,9212,6036,1362,2949,1637,7030,3737,1434,5832,5999,1783,9053,7977,159,8531,1314,5809,8796}

    Returns: -1

  59. {7431,1215,1385,8718,4063,3647,5395,1298,5053,6289,545,8488,6007,4438,6876,6596,7783,5062,4463,9408,3611,1628,3001,9385,9699,5061,7278,2286,7013,5253,3367,3220,1196,3025,3645,2148,4772,246}

    Returns: -1

  60. {8914,3323,7328,9537,4984,7465,2501,3445,5672,2019,7709,2009,9581,3953,9637,6647,6550,2225,126,3326,8088,8754,9151,9969,9353,1322,6994,438,4245,5184,9667,247,5245,7346,1540,8660,3284,8305,3339,5407,7584}

    Returns: -1

  61. {7264,6338,3599,2703,9224,4199,974,2959,7751,1002,2874,1365,8909,1826,3496,8519,8126,6311,7980,6002,34,2073,835,9989,4712,5624,7209,9171,286,5466,8419,2709,9051,6040,7062,2934,134,9809,6254,5189,4476,198,6313,5559}

    Returns: -1

  62. {9646,3804,7577,6434,4816,6989,2821,6387,3435,6264,8376,2392,6572,1852,7793,5495,306,8593,1457,1206,2340,127,512,4161,1593,4260,5273,6007,1855,4578,9897,8861,7669,2095,3892,7849,1824,1524,3072,6392,5770,9086,9048,2585,8862,4576,314}

    Returns: -1

  63. {1,2,3,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    Returns: -1

  64. {1,2,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    Returns: -1

  65. {1,1}

    Returns: -1

    The cash machine might give only the first type of "1" coin.

  66. {2,2,7}

    Returns: -1

  67. {4,6,12,17}

    Returns: -1

  68. {4,6,466,577}

    Returns: -1

  69. {23, 27, 50 }

    Returns: -1

  70. {7, 1000, 13 }

    Returns: -1

  71. {3, 5, 24 }

    Returns: -1

  72. {2, 5, 7 }

    Returns: -1

  73. {2, 3, 7 }

    Returns: -1

  74. {4, 5, 11 }

    Returns: -1

  75. {10000, 9999, 9998, 9997, 9996, 9995, 9994, 9993, 9992, 9991, 9990, 9989, 9988, 9987, 9986, 9985, 9984, 9983, 9982, 9981, 9980, 9979, 9978, 9977, 9976, 9975, 9974, 9973, 9972, 9971, 9970, 9969, 9968, 9967, 9966, 9965, 9964, 9963, 9962, 9961, 9960, 9959, 9958, 9957, 9956, 9955, 9954, 9953, 9952, 9951 }

    Returns: -1

  76. {10000, 10000, 10000, 10000, 10000, 10000, 2, 4566, 456, 256, 7556, 4465 }

    Returns: -1

  77. {2001, 2002, 2003, 3001, 3005 }

    Returns: -1

  78. {4, 5, 6, 7 }

    Returns: -1

  79. {5781, 5744, 8980, 5092, 5396, 6938, 1674, 4260 }

    Returns: 43865

  80. {5000, 3000, 7000 }

    Returns: -1

  81. {3, 5, 7, 11, 13, 17, 19, 23, 29 }

    Returns: -1

  82. {5, 7, 8 }

    Returns: -1

  83. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: -1

  84. {3, 4, 10 }

    Returns: -1

  85. {300, 301, 302, 401, 502, 2345 }

    Returns: -1

  86. {4, 7, 22 }

    Returns: -1

  87. {1234, 5678, 6912 }

    Returns: -1

  88. {20, 17, 3 }

    Returns: -1

  89. {2, 3, 5 }

    Returns: -1

  90. {5781, 5744, 8980, 5092, 5396, 6938, 1674, 4260, 300, 200, 500 }

    Returns: -1

  91. {3, 5, 8 }

    Returns: -1

  92. {3, 4, 9698 }

    Returns: -1

  93. {5781, 5744, 8980, 5092, 5396, 6938, 1674, 4260, 8756 }

    Returns: -1

  94. {3, 4, 5 }

    Returns: -1

  95. {2, 6 }

    Returns: -1

  96. {2, 3, 4, 5, 6, 7, 8, 9 }

    Returns: -1

  97. {3, 4, 14 }

    Returns: -1

  98. {3, 7, 10 }

    Returns: -1

  99. {10, 11, 13, 16, 18 }

    Returns: -1

  100. {10, 11, 13, 17 }

    Returns: -1

  101. {9951, 9952, 9953, 9954, 9955, 9956, 9957, 9958, 9959, 9960, 9961, 9962, 9963, 9964, 9965, 9966, 9967, 9968, 9969, 9970, 9971, 9972, 9973, 9974, 9975, 9976, 9977, 9978, 9979, 9980, 9981, 9982, 9983, 9984, 9985, 9986, 9987, 9988, 9989, 9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999, 10000 }

    Returns: -1

  102. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 }

    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: