Statistics

Problem Statement for "NewCoins"

Problem Statement

As a finance minister, Bob decided to make new denominations of coins. If the values of the coins are x1, x2, x3, ... in ascending order then x1 must be 1 and xb must be an integer multiple of xa for all b > a.

He has a list of products sold in his country. The price of the i-th product is price[i]. He wants to minimize the number of coins required to buy each product exactly once. Each product must be purchased separately using coins that total to exactly the value of the product. Using multiple coins of the same denomination is allowed. See example 0 for further clarification.

Return the minimal number of coins required to buy each product exactly once.

Definition

Class:
NewCoins
Method:
minCoins
Parameters:
int[]
Returns:
int
Method signature:
int minCoins(int[] price)
(be sure your method is public)

Constraints

  • price will contain between 1 and 50 elements, inclusive.
  • Each element in price will be between 1 and 100,000, inclusive.

Examples

  1. {25, 102}

    Returns: 4

    Bob can use {1, 25, 100} as the new set of coins. Then, a single coin of value 25 can be used to buy the first product. To buy the second product, one coin of value 100 and two coins of value 1 is sufficient. So, in total, 4 coins can be used to buy all products using the new set of coins.

  2. {58}

    Returns: 1

    One possible set of coins is {1, 58}.

  3. {1, 4, 5, 9, 16}

    Returns: 7

    One possible set of coins is {1, 2, 4, 8, 16}.

  4. {1, 1, 1, 1, 1}

    Returns: 5

    Different products may have the same price.

  5. {28, 569, 587, 256, 15, 87, 927, 4, 589, 73, 98, 87, 597, 163, 6, 498}

    Returns: 62

  6. {64684, 1349, 57149, 10827, 69033, 30436, 3451, 65812, 85433, 9623, 2324, 87834, 41351, 71324, 68314, 16107, 41980, 19221, 88946, 41216, 84157, 49495, 52959, 86450, 20905, 91012, 92925, 49761, 10798, 89593, 20039, 69872, 73866, 60765, 20065, 10468, 52299, 50135, 35670, 87729, 63698, 62827, 13244, 70947, 62399, 33036, 79686, 33551, 53717, 9151}

    Returns: 413

  7. {52172, 83196, 72304, 27447, 19878, 82919, 74844, 64187, 82705, 39352, 90449, 47420, 57204, 48755, 9246, 50038, 78194, 86448, 32737, 75867, 54137, 83203, 10454, 64516, 82965, 33707, 26622, 93693, 13056, 29544, 57844, 67503, 89029, 43869, 28534, 37051, 22005, 49345, 26407, 88852, 30205, 29441, 69712, 29544, 44814, 40909, 40516, 989, 62223, 3918}

    Returns: 392

  8. {62222, 63618, 90780, 15784, 93563, 59442, 26383, 31730, 70911, 34357, 48357, 19072, 69381, 50127, 27387, 84101, 93295, 32110, 67486, 78198, 97383, 60474, 14393, 18368, 47091, 49000, 27247, 27399, 54329, 47986, 36505, 11731, 17025, 34080, 41901, 29877, 35342, 96548, 672, 38049, 45497, 7586, 36380, 48345, 33489, 34021, 51099, 22227, 79532, 83254}

    Returns: 406

  9. {49960, 10660, 6113, 38113, 98031, 94909, 24159, 20776, 99388, 48568, 96232, 66358, 89969, 13047, 4100, 95097, 70314, 45918, 74075, 23416, 221, 57222, 60260, 65259, 14487, 62870, 66017, 24647, 87458, 83941, 42594, 69481, 64939, 64220, 3766, 18392, 15606, 21903, 69159, 30119, 68450, 44104, 43543, 50502, 16249, 6677, 44616, 71138, 98916, 90393}

    Returns: 395

  10. {39841, 18676, 87320, 66207, 85999, 27014, 48143, 68737, 89683, 8941, 63452, 32101, 63795, 2724, 98094, 60902, 44972, 52388, 22996, 93853, 88662, 25522, 76536, 36506, 37847, 72719, 91502, 68691, 19861, 76206, 7929, 63240, 43097, 25373, 10785, 32607, 33609, 58514, 59781, 83660, 44232, 34287, 48863, 69897, 28191, 71551, 869, 97895, 46430, 41296}

    Returns: 432

  11. {92569, 25991, 62275, 47095, 75893, 66221, 70770, 13350, 17672, 21643, 62582, 4391, 93299, 91262, 27115, 92814, 75425, 95731, 36719, 70283, 74842, 52255, 5518, 42003, 2284, 22142, 81104, 65028, 23889, 47271, 73417, 48583, 41630, 91692, 49241, 32604, 38359, 71655, 32792, 27578, 81622, 37517, 66152, 9863, 17383, 74403, 40919, 82215, 4697, 35275}

    Returns: 414

  12. {50304, 84543, 42517, 89366, 96401, 75817, 7243, 76233, 45195, 3400, 8027, 32920, 35357, 49418, 97156, 94763, 82055, 41205, 3451, 35062, 99532, 57808, 23808, 71654, 23081, 94952, 80786, 36666, 67492, 6766, 95200, 63644, 34721, 78821, 61114, 20588, 41800, 70878, 4105, 73424, 15002, 59228, 5970, 19578, 19238, 94404, 45777, 85776, 60433, 60473}

    Returns: 380

  13. {4700, 65980, 40693, 41042, 74273, 76166, 57540, 9729, 21976, 49450, 5778, 99002, 11841, 11977, 54932, 28178, 55916, 71234, 2468, 67600, 43287, 48993, 34012, 14821, 85902, 14372, 82174, 13473, 66030, 10328, 40986, 58522, 40277, 74191, 20073, 78762, 86249, 16072, 66721, 33748, 87073, 29250, 6658, 41074, 45499, 58119, 84386, 56625, 6857, 3998}

    Returns: 356

  14. {44669, 7115, 25480, 3476, 18037, 78580, 63560, 60165, 32090, 78182, 3843, 36562, 98290, 99704, 30873, 94916, 41596, 66327, 40053, 59190, 27985, 20236, 69526, 9502, 70598, 55708, 74044, 28197, 93224, 63191, 55403, 27674, 97407, 38710, 5968, 65877, 80247, 83097, 62266, 31280, 30264, 14946, 56571, 65709, 40521, 61531, 10708, 36623, 27023, 24323}

    Returns: 398

  15. {84179, 17934, 35197, 5293, 77507, 7632, 56242, 40151, 13213, 41712, 74377, 29339, 25794, 31555, 84378, 92530, 56060, 73512, 57813, 83226, 16862, 35806, 63148, 17994, 66204, 52630, 81174, 11622, 18154, 5200, 30558, 78360, 28220, 74956, 82676, 83277, 4209, 71906, 84070, 14993, 94025, 314, 52822, 98568, 95475, 50275, 96241, 10119, 64378, 93584}

    Returns: 399

  16. {47695}

    Returns: 1

  17. {88588, 76653}

    Returns: 8

  18. {4950, 53550, 17480}

    Returns: 10

  19. {35238, 32710, 57994, 45581}

    Returns: 27

  20. {7860, 36662, 91371, 68212, 43959}

    Returns: 31

  21. {60266, 14394, 4235, 8260, 84735, 68096}

    Returns: 34

  22. {13083, 54352, 42657, 45347, 24122, 24186, 31653}

    Returns: 52

  23. {12803, 26595, 56815, 70003, 49312, 54979, 74711, 29393}

    Returns: 59

  24. {85834, 61947, 45139, 39745, 4477, 79276, 94525, 41665, 53744}

    Returns: 64

  25. {53350, 34992, 65133, 72405, 55680, 7773, 666, 95909, 56417, 44461}

    Returns: 74

  26. {96190, 93280, 93480, 94310, 94488, 93445, 91719, 93696, 98361, 91315, 96332, 95296, 90026, 90603, 91861, 96975, 93262, 97188, 92948, 92443}

    Returns: 146

  27. {94831, 96466, 97594, 98834, 91922, 99114, 95291, 95148, 95797, 91847, 96288, 98261, 99043, 91112, 92323}

    Returns: 111

  28. {92317, 94913, 98143, 91202, 91297, 95750, 95862, 94675, 91950, 97387, 93748, 93246, 92393, 96449, 93458, 96754, 97061, 99313, 92456, 98254, 93492, 90380, 95332, 91535, 99319, 99588, 94301, 96845, 99299, 97318, 93320, 98534, 90707, 91680, 97302, 96319, 90999, 99118, 97303, 92881}

    Returns: 292

  29. {97737, 91969, 95373, 93707, 96014, 99677, 96139, 94821, 91338, 93095, 98433, 90673, 93383, 93521, 94282, 91567, 95599, 92135, 93557, 98571}

    Returns: 150

  30. {96524, 94453, 91419, 94775, 91509, 90468, 94759, 95005, 95120, 91134, 90423, 94739, 98162, 97081, 98551, 93399}

    Returns: 121

  31. {92966, 94258, 91140, 97000, 96913, 94942, 90083, 96979, 96936, 97044, 94409, 98907, 96067, 94051, 91922, 95644, 95101, 99113, 90003, 91455, 97866, 97423, 97831, 93448, 95645, 90669}

    Returns: 192

  32. {90622, 99341, 90665, 96820, 93675, 96114, 90324, 99654, 92654, 95158, 91280, 91970, 95816, 99724, 96047, 99321, 90179, 92528, 94267, 96303, 97916, 94287, 94090, 92030, 93860, 94730, 97200, 97062, 94849, 94845, 98883, 97237, 96372, 91749, 95606, 94908, 97885, 99529, 91692, 98012, 95883, 96241, 94234}

    Returns: 324

  33. {93537, 99651, 92057, 94135, 96265, 94025, 95392, 94736, 94603, 94189, 98354, 97518, 98900, 91599, 99749, 93981, 93005, 91649, 99309, 99247, 90115}

    Returns: 155

  34. {94991, 93096, 95735, 94018, 97452, 97098, 93924, 93052, 95017, 90778, 97701, 94252, 94526}

    Returns: 96

  35. {91371, 93413, 93039, 96137, 93681, 95744, 94660, 93682, 90378, 96898, 96387, 98627, 90806, 91665, 90238, 97370, 95495, 95321, 95738, 90935, 92451, 93957, 95583, 92792, 95319, 95683, 90938, 93274, 90882, 93781, 95831, 98764, 95206, 94131, 90849, 92804, 99780, 98799, 96786, 98205}

    Returns: 295

  36. {75, 70, 82, 1, 26, 29, 97, 76, 97, 14, 82, 39, 61, 41, 26, 34, 38, 61, 46, 72, 6, 45, 93, 27, 68, 95, 85, 6, 43, 50, 69, 71, 73, 88, 1, 75, 41, 98, 2, 57, 49, 48, 66}

    Returns: 136

  37. {63, 77, 57, 62, 26, 98, 84, 20, 85, 4, 3, 20, 42, 67, 93, 40, 59, 20, 47, 67, 98, 30, 80, 60, 94, 19, 30, 66, 38, 84, 37, 81}

    Returns: 106

  38. {27, 16, 65, 99, 42, 72, 64, 47, 8, 89, 33, 80, 57, 21, 26, 51, 54, 23, 82, 9, 55, 4, 51, 19, 53, 8, 11, 26, 64, 38, 71, 2, 52, 4, 92, 3}

    Returns: 101

  39. {83, 23, 96, 24, 30, 5, 6, 47, 23, 38, 8, 10, 98, 41, 96, 66, 92, 68, 92, 45, 11, 8, 18, 49, 100, 44, 90, 60, 51, 63, 46, 20, 8, 27, 8, 80, 53}

    Returns: 110

  40. {88, 24, 41, 6, 48, 68, 25, 49, 79, 2, 88, 36, 17, 63, 54, 54, 22, 45, 3, 87, 35, 84}

    Returns: 67

  41. {16, 51, 94, 23, 87, 58, 91, 54, 32, 84, 14, 83, 72, 35, 27, 34, 34, 52, 58}

    Returns: 63

  42. {35, 23, 25, 13, 4, 55, 74, 5, 83, 86, 34, 93, 46, 77, 92, 69, 38, 70, 42, 34, 54, 34, 39, 69, 28, 35, 48, 56, 41, 54, 85, 21, 51, 89, 59, 88, 33, 76, 17, 24, 50, 82, 50, 12, 8, 14, 41}

    Returns: 146

  43. {5, 13, 39, 45, 95, 84, 27, 65, 99, 50, 90, 86, 51, 32, 45, 20, 36, 60, 18, 78, 37, 30, 88, 6, 4, 55, 64, 10, 60, 26, 8, 78, 55, 33, 28, 92, 6, 42, 23, 96, 60, 82, 15, 26, 8, 32}

    Returns: 140

  44. {100, 24, 83, 24, 86, 32, 98, 16, 15, 68, 29, 3, 81, 33, 93, 2, 74, 92, 70, 9, 78, 87, 5, 5, 82, 82, 81, 5, 23, 24, 97, 42, 80, 23}

    Returns: 97

  45. {93, 78, 26, 50, 54, 25, 94, 73, 48, 2, 76, 93, 37, 95, 21, 46, 35, 46, 35, 5, 52, 22, 78, 39, 75, 8, 64, 3, 51, 98, 48, 51, 30, 52, 60, 13, 14, 9, 47, 17, 38, 59, 84, 43, 62, 46, 12, 16, 11, 70}

    Returns: 163

  46. {99833, 99623, 99877, 99829, 99487, 99767, 99661, 99733, 99497, 99551, 99529, 99859, 99761, 99961, 99439, 99817, 99431, 99793, 99823, 99971, 99787, 99469, 99989, 99907, 99643, 99719, 99713, 99679, 99923, 99563, 99991, 99523, 99571, 99929, 99689, 99527, 99839, 99581, 99707, 99709, 99721, 99809, 99881, 99611, 99667, 99871, 99607, 99901, 99559, 99577}

    Returns: 324

  47. {99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991, 99991}

    Returns: 50

  48. {1}

    Returns: 1

  49. {100000}

    Returns: 1

  50. {100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000}

    Returns: 50

  51. {99972, 99995, 99988, 99963, 99983, 99984, 99957, 99977, 99960, 99956, 99990, 99982, 99965, 100000, 99992, 99970, 99967, 99974, 99958, 99971, 99976, 99952, 99986, 99999, 99991, 99979, 99951, 99975, 99968, 99955, 99997, 99961, 99993, 99981, 99980, 99994, 99969, 99998, 99987, 99978, 99966, 99973, 99989, 99964, 99962, 99985, 99959, 99996, 99953, 99954}

    Returns: 216

  52. {25071,33716,36796,39039,42110,43628,44906,45455,46065,46509,47065,47951,48071,48761,55163,57085,57599,58748,59323,59477,60230,61375,62193,64331,64799,64821,71343,71665,72431,73319,74640,76699,77708,79033,79751,80117,83973,86963,89837,94367,96995,97242,97667,98799,98934,99007,99250,99293,99359,99898}

    Returns: 494

  53. {30593,36862,40170,44519,44906,45455,46509,47951,48071,48761,52148,54514,54589,55163,56976,57085,57259,57599,59323,59903,60230,61029,61145,61375,62935,64799,68703,71153,71343,72142,72431,72889,73319,76638,79033,79820,79841,80117,81517,81638,86963,89837,94367,97242,97667,99007,99250,99293,99359,99898}

    Returns: 513

  54. {30593,36862,40170,44519,45455,46509,47951,48071,48761,52148,54514,54589,55163,56976,57085,57259,57599,59323,59903,61029,61145,61375,62935,64799,68703,71153,71343,72142,72431,72889,73319,79033,79820,79841,80117,81517,81638,86963,88988,89837,90838,93125,94367,97242,97667,99007,99250,99293,99359,99898}

    Returns: 514

  55. {30593,35639,36862,40170,44519,45455,46509,47951,48071,48761,52148,54589,55163,56976,57085,57259,57599,59323,59903,61029,61145,61375,62935,64799,68703,71153,71343,72142,72431,72889,73319,79033,79820,79841,80117,81517,81638,86963,88988,89837,90838,93125,94367,97242,97667,99007,99250,99293,99359,99898}

    Returns: 515

  56. {30593,35639,36862,40170,40603,44519,45455,46509,47951,48071,48761,52148,54589,55163,56976,57085,57259,57599,59323,59903,61029,61145,61375,62935,64799,68703,71343,72142,72431,72889,73319,79033,79820,79841,80117,81517,81638,86963,88988,89837,89839,90838,93125,94367,97667,99007,99250,99293,99359,99898}

    Returns: 517

  57. {24569,30319,31874,35639,36862,39519,44519,47951,48563,48761,48956,54589,54989,55151,55163,57085,57259,57599,59903,60379,61145,61375,62935,64799,68983,71343,72142,72431,72701,79841,80117,80339,80347,81357,81517,81638,86012,86399,87659,89837,89839,90838,91951,92117,93125,94367,95037,97667,99007,99359}

    Returns: 544

  58. {24569,29951,30319,35639,36862,39519,40822,44519,47951,48563,48956,50399,54589,54899,54989,55151,55163,57085,57259,57599,59903,60379,61145,61375,62935,64799,68983,71343,72142,72431,72701,77747,80117,80339,81357,81517,81638,86012,86399,87659,89837,89839,91951,92117,93125,94367,95037,97667,99007,99359}

    Returns: 550

  59. {24569,29951,30319,35639,36862,40822,44519,48563,48956,50399,54589,54989,55151,57085,57259,57599,59903,60143,60379,61145,61375,62579,62935,64799,68983,71343,72142,72701,76799,77535,77747,78335,78839,80117,80339,81395,81517,81638,82943,82943,85739,86012,86399,89837,89839,91951,92117,95037,96694,99359}

    Returns: 563

  60. {24569,29951,30319,35639,36862,40822,44519,48956,50399,54589,54989,55151,57085,57259,57599,59903,60143,60379,61145,61375,62579,62935,64799,68983,71343,72142,72701,73709,76799,77535,77747,78335,78839,80117,80339,81395,81517,81638,82943,82943,85739,86012,86399,89837,89839,91951,92117,95037,96694,99359}

    Returns: 565

  61. {103, 618, 619, 620, 4326, 4327, 4328, 4329, 4330, 4331, 4332, 8652, 8653, 8654, 8655, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 95172, 99603, 99602, 99499, 99498, 95276, 95275, 95176, 95175, 95174, 95173, 95172, 95172, 95172, 10609 }

    Returns: 107

  62. {52964, 55425, 18870, 53993, 20605, 57492, 3243, 22307, 96768, 96104, 64065, 90084, 53985, 55686, 9437, 28268, 19203, 53054, 14219, 63147, 47326, 33278, 32952, 16171, 78520, 69102, 1127, 67064, 75470, 54691, 6390, 23030, 11516, 78691, 56332, 53919, 20908, 46493, 30108, 70872, 28384, 97020, 77452, 84273, 46852, 25525, 20510, 75777, 69176, 80605 }

    Returns: 397

  63. {32173, 64403, 31183, 52541, 15791, 98927, 39521, 21569, 48779, 67307, 10847, 2473, 66749, 11197, 84659, 39839, 21851, 36389, 53527, 44893, 40123, 16361, 48313, 34421, 33247, 38561, 69847, 8641, 9967, 25409, 54983, 63949, 2531, 60317, 49747, 66431, 27827, 16943, 55001, 65521, 67421, 87973, 2879, 19219, 72859, 8609, 45337, 59729, 45247, 23893 }

    Returns: 444

  64. {28, 569, 587, 256, 15, 87, 927, 4, 589, 73, 98, 87, 597, 163, 6, 498, 95959, 93047, 93444, 2739, 1263, 1111, 2222, 3333, 4444, 5555, 6666, 777, 27936 }

    Returns: 146

  65. {100000, 99999, 99998, 99997, 99996, 99995, 99994, 99993, 99992, 99991, 99990, 99989, 99988, 99987, 99986, 99985, 99984, 99983, 99982, 99981, 99980, 99979, 99978, 99977, 99976, 99975, 99974, 99973, 99972, 99971, 99970, 99969, 99968, 99967, 99966, 99965, 99964, 99963, 99962, 99961, 99960, 99959, 99958, 99957, 99956, 99955, 99954, 99953, 99952, 99951 }

    Returns: 216

  66. {1, 18, 51, 104, 512, 46515, 51, 1, 18, 51, 104, 512, 46515, 51, 1, 18, 51, 104, 512, 46515, 51, 1, 18, 51, 104, 512, 46515, 51, 1, 18, 51, 104, 512, 46515, 51, 1, 18, 51, 104, 512, 46515, 51, 1, 18, 51, 104, 512, 46515, 51, 1 }

    Returns: 113

  67. {83700, 1862, 10227, 28028, 61094, 40374, 18207, 71387, 16715, 29397, 9893, 54716, 80348, 8493, 45146, 26609, 61105, 66938, 26960, 18564, 49465, 56733, 75678, 59537, 73570, 82904, 51516, 55296, 94016, 15002, 78957, 56157, 9039, 60349, 86486, 73321, 57406, 23280, 59469, 52350, 97782, 53465, 20472, 76317, 14212, 55706, 24662, 92484, 92290, 12186 }

    Returns: 409

  68. {41, 18467, 6334, 26500, 19169, 15724, 11478, 29358, 26962, 24464, 5705, 28145, 23281, 16827, 9961, 491, 2995, 11942, 4827, 5436, 32391, 14604, 3902, 153, 292, 12382, 17421, 18716, 19718, 19895, 5447, 21726, 14771, 11538, 1869, 19912, 25667, 26299, 17035, 9894, 28703, 23811, 31322, 30333, 17673, 4664, 15141, 7711, 28253, 6868 }

    Returns: 365

  69. {9990, 35597, 8749, 68536, 64760, 36658, 71274, 66777, 59114, 52894, 31447, 8487, 44827, 81859, 61296, 91299, 46012, 49169, 79440, 83845, 71592, 65647, 307, 3613, 63202, 83495, 25063, 72789, 53994, 45338, 44527, 83731, 24667, 83253, 4051, 14107, 19204, 73916, 17416, 84432, 84353, 18243, 73911, 66331, 95605, 79452, 28685, 12548, 93606, 57834 }

    Returns: 396

  70. {83001, 86001, 77001, 15001, 93001, 35001, 86001, 92001, 49001, 21001, 62001, 27001, 90001, 59001, 63001, 26001, 40001, 26001, 72001, 36001, 11001, 68001, 67001, 29001, 82001, 30001, 62001, 23001, 67001, 35001, 29001, 2001, 22001, 58001, 69001, 67001, 93001, 56001, 11001, 42001, 29001, 73001, 21001, 19001, 84001, 37001, 98001, 24001, 15001, 70001 }

    Returns: 221

  71. {28, 569, 587, 256, 15, 87, 927, 4, 589, 73, 98, 87, 597, 163, 6, 498 }

    Returns: 62

  72. {29950, 19951, 39952, 19953, 96954, 89955, 19956, 49957, 29958, 93959, 39960, 83961, 90962, 38963, 71964, 65965, 39966, 99967, 79968, 76969, 49370, 59971, 49972, 41973, 64974, 39975, 38976, 19977, 49978, 59979, 59680, 54981, 72982, 53983, 26984, 29985, 59986, 39987, 59848, 3989, 64990, 42991, 29992, 79993, 11994, 19995, 95961, 29997, 19998, 100000 }

    Returns: 384

  73. {58410, 98650, 94087, 96997, 84163, 72512, 25524, 62491, 62482, 76432, 91952, 5178, 63371, 42304, 89158, 88390, 44656, 95313, 35414, 39905, 58091, 45091, 44898, 48854, 53703, 93990, 32821, 83890, 12620, 38224, 17936, 85133, 39221, 60651, 30354, 84327, 38607, 33382, 54628, 61965, 44753, 1419, 98462, 67514, 5811, 46289, 86873, 66842, 62924, 50280 }

    Returns: 396

  74. {100000, 99999, 99998, 99997, 99996, 99995, 99994, 99993, 99992, 99991, 99990, 99989, 99, 999, 9999, 99985, 99984, 99983, 99982, 99981, 99980, 99979, 99978, 99977, 99976, 99975, 99974, 99973, 99972, 99971, 99970, 99969, 99968, 99967, 99966, 99965, 99964, 99963, 99962, 99961, 99960, 99959, 99958, 99957, 99956, 99955, 99954, 99953, 99952, 99951 }

    Returns: 252

  75. {99947, 99993, 99987, 99991, 99966, 99946, 99915, 99927, 99930, 99969, 99979, 99974, 99905, 99915, 99912, 99924, 99932, 99960, 99993, 99934, 99947, 99929, 99901, 99944, 99929, 99908, 99916, 99965, 99943, 99903, 99958, 99931, 99993, 99917, 99900, 99905, 99958, 99925, 99932, 99981, 99958, 99906, 99947, 99905, 99983, 99983, 99931, 99919, 99942, 100000 }

    Returns: 226

  76. {42, 18468, 6335, 2, 5, 100000, 11479, 29359, 26963, 99999, 5706, 28146, 23282, 16828, 9962, 492, 2996, 11943, 4828, 5437, 32392, 14605, 3903, 154, 293, 12383, 17422, 18717, 19719, 19896, 5448, 21727, 14772, 11539, 1870, 19913, 25668, 26300, 17036, 9895, 28704, 23812, 31323, 30334, 17674, 4665, 15142, 7712, 28254, 6869 }

    Returns: 347

  77. {90001, 90007, 90011, 90017, 90019, 90023, 90031, 90053, 90059, 90067, 90071, 90073, 90089, 90107, 90121, 90127, 90149, 90163, 90173, 90187, 90191, 90197, 90199, 90203, 90217, 90227, 90239, 90247, 90263, 90271, 90281, 90289, 90313, 90353, 90359, 90371, 90373, 90379, 90397, 90401, 90403, 90407, 90437, 90439, 90469, 90473, 90481, 90499, 90511, 90523 }

    Returns: 316

  78. {67167, 32221, 27829, 60096, 69303, 21320, 70884, 59253, 58744, 26630, 80930, 60560, 82364, 57526, 79844, 48389, 37040, 73383, 39499, 57117, 69645, 83576, 81772, 71119, 77054, 47480, 78537, 24769, 6144, 74469, 51670, 2442, 53788, 23920, 73044, 38514, 66861, 5207, 64536, 17359, 42240, 77704, 98020, 73353, 26798, 50788, 95371, 90870, 17411, 83832 }

    Returns: 398

  79. {100000, 39875, 48374, 87589, 43545, 34534, 32423, 23423, 12345, 65536, 30985, 100000, 124, 14559, 49327, 29512, 89987, 87678, 56748, 39875, 37819, 12678, 60980, 10000, 24578, 123, 1, 1, 1, 1, 5678, 98368, 13859, 99999, 99990, 12465, 45789, 5894, 56, 65, 10001, 20000, 30000, 58392, 44444, 55555, 66666, 99988, 12987, 300 }

    Returns: 316

  80. {1, 1, 1, 1, 1, 100000, 100000, 56546, 56464, 34, 57674 }

    Returns: 32

  81. {100000 }

    Returns: 1

  82. {1233, 23422, 2344, 345, 34534, 45666, 45555, 3455, 34534, 34534, 23444, 2344, 12333, 1233, 123, 34535, 54666, 4566, 45664, 546, 456, 456, 567, 567, 678, 768, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99998, 99993, 99991, 99992, 99999, 99999, 99999, 99999, 234, 2344, 53452, 34444, 333 }

    Returns: 318

  83. {99000, 99001, 99002, 99003, 99004, 99005, 99006, 99007, 99008, 99009, 99010, 99011, 99012, 99013, 99014, 99015, 99016, 99017, 99018, 99019, 99020, 99021, 99022, 99023, 99024, 99025, 99026, 99027, 99028, 99029, 99030, 99031, 99032, 99033, 99034, 99035, 99036, 99037, 99038, 99039, 99040, 99041, 99042, 99043, 5, 6, 125, 3333 }

    Returns: 185

  84. {5444, 31525, 75309, 51567, 6097, 11026, 60444, 4588, 92263, 47709, 91181, 21626, 48895, 21373, 58744, 96319, 43795, 6697, 38812, 15655, 3620, 48926, 22393, 88288, 95477, 75837, 69590, 57692, 80270, 41323, 44412, 45683, 4475, 54383, 8153, 24862, 73770, 27671, 64318, 23197, 18768, 88979, 5057, 59153, 8325, 74424, 860, 94371, 11331, 91486 }

    Returns: 412

  85. {100000, 1 }

    Returns: 2

  86. {16735, 22078, 31867, 70058, 94551, 53963, 84364, 23461, 26341, 20015, 74696, 60486, 99629, 30605, 87225, 55805, 68025, 78549, 31434, 23435, 19540, 74487, 29097, 49331, 39740, 2604, 91602, 82771, 34501, 40203, 52018, 46113, 62280, 83884, 16171, 51708, 32724, 95411, 75168, 59064, 15426, 44741, 19550, 9933, 75346, 1653, 65737, 38248, 80201, 92047 }

    Returns: 407

  87. {98765, 12345, 99999, 31321, 32132, 23213, 23232, 32321, 33333, 88888, 77777, 66666, 55555, 44444, 33331, 12345, 98765, 12345, 1001, 32146, 97532, 23154, 42356, 23441, 45222 }

    Returns: 188

  88. {7823, 6478, 3098, 40349, 75983, 47094, 81376, 98465, 98276, 89413, 75986, 41987, 56243, 94728, 39758, 93475, 98473, 15891, 74589, 4362, 59763, 42956, 34638, 72461, 82936, 5149, 3056, 94321, 59614, 98564, 76715, 10443, 6723, 65614, 2756, 40678, 557, 4137, 99999, 99997, 10000, 25000, 12345, 65535, 98765, 65534, 72384, 2873, 23984, 23741 }

    Returns: 398

  89. {51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000, 51867, 18453, 18473, 48351, 100000 }

    Returns: 300

  90. {99950, 99951, 99952, 99953, 99954, 99955, 99956, 99957, 99958, 99959, 99960, 99961, 99962, 99963, 99964, 99965, 99966, 99967, 99968, 99969, 99970, 99971, 99972, 99973, 99974, 99975, 99976, 99977, 99978, 99979, 99980, 99981, 99982, 99983, 99984, 99985, 99986, 99987, 99988, 99989, 99990, 99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999 }

    Returns: 215

  91. {62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636, 62337, 32723, 100000, 99999, 63636 }

    Returns: 310

  92. {100000, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 100000, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 100000, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 100000, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 100000, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999 }

    Returns: 55

  93. {76162, 77317, 97093, 94619, 92425, 87392, 78503, 75098, 72028, 87543, 73587, 76164, 92787, 70193, 99204, 81239, 86051, 88549, 77154, 97039, 76362, 82370, 98835, 70965, 81229, 70846, 88372, 89174, 72084, 88045, 89928, 87077, 96883, 83909, 94799, 98723, 70525, 71775, 76955, 86190, 75220, 96049, 70111, 86520, 93172, 77594, 70281, 98570, 85201, 81549 }

    Returns: 417

  94. {45341, 9730, 97708, 17342, 8046, 57129, 45129, 70079, 35866, 18438, 51019, 65834, 83336, 64405, 56026, 90875, 9646, 41174, 88005, 47964, 4585, 12117, 38168, 81975, 91066, 62184, 74786, 68588, 25858, 16110, 15598, 54121, 14240, 38368, 93058, 97955, 50032, 68648, 61871, 28421, 27488, 70917, 100000, 23012, 58205, 13376, 87283, 57111, 80424, 19600 }

    Returns: 400

  95. {100000, 99999, 99998, 99997, 99996, 99995, 99994, 99993, 99992, 99991, 99990, 99989, 99988, 99987, 99986, 99985, 99983, 99982, 99981, 99980, 99979, 99978, 99977, 99976, 99975, 99974, 99973, 99972, 99971, 99970, 99969, 99968, 9, 9967, 99966, 99965, 99964, 99963, 99962, 99961, 99960, 99959, 99958, 99957, 99956, 99955, 99954, 99953, 99952, 99951 }

    Returns: 250

  96. {12380, 94645, 64840, 3741, 93844, 45825, 76857, 77148, 72652, 36543, 80476, 21971, 51192, 24824, 58127, 97091, 88157, 90519, 25890, 90711, 91115, 13889, 49959, 88301, 75617, 64243, 45571, 43079, 60063, 46215, 96903, 43694, 88051, 67828, 65530, 32362, 62515, 27417, 32596, 73882, 44939, 32083, 10071, 42456, 45689, 92159, 57386, 82798, 45958, 16470 }

    Returns: 423

  97. {98765, 12345, 99999, 31321, 32132, 23213, 23232, 32321, 33333, 88888, 77777, 66666, 55555, 44444, 33331, 12345, 98765, 12345, 1001, 32146, 97532, 23154, 42356, 23441, 45222, 40000, 407, 403, 90007, 12361 }

    Returns: 218

  98. {25, 102 }

    Returns: 4

  99. {100000, 80000, 60000, 49999, 39999, 43242, 24111, 43214, 11111, 5555, 42424, 12323, 21434, 12311, 22212, 22222, 33333, 44444, 55555, 66666, 5, 7, 999, 777, 54, 545, 344, 333, 666, 444, 555, 3453, 5543, 232, 111, 232, 3213, 2131, 11, 1, 22, 223, 333, 444, 6643, 234, 222, 1123, 3312, 313 }

    Returns: 303

  100. {100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000 }

    Returns: 50

  101. {100000, 99999, 99998, 99997, 99996, 99995, 99994, 99993, 99992, 99991, 99990 }

    Returns: 31

  102. {1, 2, 3, 4, 5, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 34928, 37089, 39250, 41411, 43572, 45733, 47894, 50055, 52216, 54377, 56538, 58699, 60860, 63021, 65182, 67343, 69504, 71665, 73826, 75987, 78148, 80309, 82470, 84631, 86792, 88953, 91114, 93275, 95436, 97597, 99758, 100000 }

    Returns: 305

  103. {97425, 91673, 95489, 93500, 96027, 97570, 90072, 95275, 96049, 97639, 91363, 92171, 91288, 90453, 92639, 95132, 91778, 95258, 98000, 96524, 91196, 92123, 98753, 90190, 97730, 99428, 96472, 94841, 91704, 95090, 94748, 90966, 90723, 95437, 99180, 98900, 90639, 93128, 92628, 93206, 98096, 93045, 90257, 96035, 97961, 92537, 96415, 99621, 96399, 99944 }

    Returns: 366

  104. {1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 12 }

    Returns: 14

  105. {14536, 99998, 99990, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 100000, 99999, 99999, 99999, 99999 }

    Returns: 121

  106. {23070, 27465, 25955, 3630, 77052, 37623, 43421, 25952, 8120, 57669, 370, 88809, 44395, 9284, 10907, 47358, 67618, 68751, 18592, 40902, 21271, 92442, 69748, 30361, 23556, 17642, 53580, 29986, 26678, 27028, 84393, 99613, 10411, 6240, 68044, 37673, 10171, 55713, 77310, 29749, 57643, 40304, 58989, 62621, 55442, 73248, 9317, 9556, 16416, 34566 }

    Returns: 375

  107. {2, 26 }

    Returns: 2

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: