Statistics

Problem Statement for "BirthdayCandy"

Problem Statement

Elisa is a primary school student. Tomorrow it's her birthday!

In Elisa's country it is customary that when it's your birthday, you are supposed to bring candy for everyone. Hence, Elisa's mother is now taking Elisa to buy a bag of candy for tomorrow.

Social protocol dictates that candy is always given out to classmates using the following algorithm: 

repeat:
    if there is still enough candy for everyone (including you):
        give everyone else one candy
        take one candy for yourself
    else:
        stop (and you get to keep the candy that remained in the bag)

You know that there are K other kids in Elisa's class.

The store carries different brands of candy. You are given their description in the int[] candy. Each element of candy is the number of pieces of candy in one of the bags available at the store. Find out which bag should Elisa choose if she wants the most candy for herself. Return the number of pieces of candy she will get to keep if she chooses the bag wisely.

Definition

Class:
BirthdayCandy
Method:
mostCandy
Parameters:
int, int[]
Returns:
int
Method signature:
int mostCandy(int K, int[] candy)
(be sure your method is public)

Constraints

  • K will be between 1 and 50, inclusive.
  • candy will have between 1 and 50 elements, inclusive.
  • Each element of candy will be between 1 and 1000, inclusive.

Examples

  1. 9

    {23, 7}

    Returns: 7

    If Elisa buys the bag with 23 candies, the following will happen: 23 is enough to give everyone a candy, so she gives everyone else a candy and then takes one herself. 13 is enough to give everyone a candy, so she gives everyone else a candy and then takes one herself. 3 is no longer enough to give everyone a candy, so she keeps the remaining 3 candies. In total, she would have 1+1+3 = 5 candies. On the other hand, if she buys the bag with 7 candies, she will get to keep all of them.

  2. 1

    {1, 2}

    Returns: 1

    Here it does not matter which bag Elisa buys. In either case she will end with a single candy.

  3. 4

    {43, 81, 17, 1, 9}

    Returns: 17

  4. 6

    {7}

    Returns: 1

  5. 9

    {4,5,6,7,8,9,10,11,12,13,14,15,16}

    Returns: 9

  6. 23

    {665,714,512,780,619}

    Returns: 47

  7. 3

    {672,980,2,967,740,938,583,233,534,453,34,734,614,569,244,130,102,595,522,97,950,223,760,791,618,690,901}

    Returns: 245

  8. 36

    {441,668,574,691,329,939,710,753,475,331,176,10,634,91,626,582,409}

    Returns: 50

  9. 39

    {838,670,900,36,293,467,891,230,248,128,956,473,486,348,7,524,441}

    Returns: 59

  10. 17

    {149,862,969}

    Returns: 68

  11. 13

    {890,821,128,274,612,79,431,104,210,158,92,549,954,989,485,149,873,994,202,747,541,877,239,911,836,825,34,124,516,876,208,439,590,826,178,819,500,976,50,349,504,470,860,123,190,862,653,552,375,155}

    Returns: 79

  12. 33

    {429,601,924,889,945,377,377,697,285,319,495,504,343,166,1,471,572,662,312,313}

    Returns: 54

  13. 11

    {523,651,777,784,488,33,585,911,923,955,944,274,576,285,285,115,624,343,273,600,950,116,588,595,706,575,188,613}

    Returns: 87

  14. 6

    {739,188,313,892,788,164,942,584,352,713,134,870,184,874,163,52,144,403,375,460,550,207,107,318,430,847,718}

    Returns: 138

  15. 16

    {606,870,359,173,260,89,549,787,70,148,946,132,313,742,835,707,103,208,359,911,846,555,883,574,694,472,797,23,341,659,972,479,112,460,362,999,526,526,126,204,593}

    Returns: 71

  16. 21

    {951,398,85,419,921,924,363,281,297,510}

    Returns: 60

  17. 13

    {68,541,538,202,747,886,81,871,482,111,48,348,747,925,627,609,113,844,114,367,763,354,1,18,955,957,843,594,66}

    Returns: 73

  18. 42

    {579,753,6,19,81,291,817,78,777,545,263,384,548,475,105,836,82,631,580,994,370,479,970,527,388,36,939,266,745,86,586,586,782,196,772,618,901,176}

    Returns: 61

  19. 3

    {245,72,140,529,626,583,563,624,169,953,868,154,631,919,470,419,621,15,827,503,350,570,818,403,38,147,400,852,604,378,677,2,357,632,819,494,150,966}

    Returns: 243

  20. 22

    {969,320,272,331,973,689,769,223,532,212,835,800,769,940,788,927,57,557,732,236,596,84,477,784,371,205,754}

    Returns: 60

  21. 43

    {390,535,387,491,551,914,326,390,965,476,83,282,636,141}

    Returns: 62

  22. 38

    {333,318,364,56,754,265,589,469,817,162,526,299}

    Returns: 57

  23. 49

    {113,385,135,669,523,155,529,349,191,134,548,944,764}

    Returns: 62

  24. 4

    {393,339,75,328,646,659,622,408,661,782,731,731,241,960,39,654,334,376,439,774,434}

    Returns: 192

  25. 12

    {538,301,820,58,778,745,168,831,447,479,362,703,425,629,758,263,304,381,55,956,44,23,472,916,874,761,79,219,670,302,71,749,872,923,904,904,977,272,394,523,933,827,462,421,872,376,428,364}

    Returns: 81

  26. 9

    {887,941,418,943,411,338,204,462,952,102,78,229,828,789,134,55}

    Returns: 97

  27. 12

    {745,160,334,828,246,224}

    Returns: 72

  28. 46

    {367,439,19,283,622,420,717,658,557,354,763,246,896,302,918,959,416,113,331,829,438,452,246,818,676,462,66,89,133,918,878,620,588,362,825}

    Returns: 52

  29. 45

    {793,393,481,162,606,119,337,16,783,485,801,372,969,333,896,511,997,385,897,279,399,364,171,425,569,873,309,378,250}

    Returns: 63

  30. 10

    {672,400,215,949,310,125,728,653,45,965,311,146,699,422,16,512,133,466}

    Returns: 95

  31. 35

    {656,283,624,866,838,20,275,986,283,408,963,209,698,62,518}

    Returns: 53

  32. 28

    {42,930,905,731,7,915,26,880,570,979,940,427,93,401,917,827,742,729,765,22,967,198,693,955,704,289,93,105,486,469,695,674,239,202,243,91,331,509,135,990,445,868,980,467,662,464,994,857,869,272}

    Returns: 59

  33. 9

    {260,120,497,268,869,205,78,952,703,617,540,897,883,659,418,286,947,172,213,420,758,943,707,204,666,837,706,870,219,546,48,60,771,267,248,48,981,25,337,351,961,457,14}

    Returns: 101

  34. 37

    {543,130,447,69,838,499,849,430,303,165,602,880,376,918,981,230,184,928,169,427,426,179,530,970,809,746,6,504,802,122}

    Returns: 56

  35. 7

    {819,26,846,97,839}

    Returns: 111

  36. 48

    {158,532}

    Returns: 52

  37. 47

    {209,344,72,266,817,111,795,808,916}

    Returns: 56

  38. 50

    {379,420,70,62,84,478,708,513,608,448,288,345,34,728,434,765,549,668,141,523,429,192,242}

    Returns: 58

  39. 29

    {636,509,531,877,905,792,361,601,452,218,465,864,259,202,18,639,68,716,701,329,173,482,917,974,649}

    Returns: 52

  40. 25

    {471,741,983,423,415,57,76,514,691,396,100}

    Returns: 58

  41. 18

    {263,48,327,497,140,632,841,725,485,323,852,654,879,608,776,712,693,811,702,447,294,257,486,823,163,608,555,657,477,97,678,966,176,993,534,258,829,243}

    Returns: 66

  42. 45

    {955,702,47,495,300}

    Returns: 55

  43. 1

    {569,965,236,254,395,603,997,431,34}

    Returns: 499

  44. 10

    {504,753,198,902,186,255,66,984,286,706,38,356,585}

    Returns: 94

  45. 29

    {845,316,810,269,345,268,791,30,876,596,308,591,785,628,198,718,443,409,884,337,510,192,101,104,63,490,401,11,426,365,637,747,111,214,979,790,704,944,948,328,73,986,611,815,943,71,589}

    Returns: 58

  46. 16

    {261,100,726,635,527,347,214,798,908,29,766,554,605,390,494,617,819,223,620,408,870,577,844,795,283,994,752,531,667,995,307}

    Returns: 67

  47. 39

    {474,999,519,996,828,719,920,338,616,995,944,212,506,909,58,606,659,903,675,285,724,48,340,525,279,738,261,154}

    Returns: 63

  48. 14

    {927,346,945,388,125,74,841,127,407,122,133,363,354,419,761,906,72,318,100,646,518,897,853,783,933,504,977,739,341,304,45,363,160,838,428,14,977,476,891,173,325,739,649,772,169,544,954,238,612,995}

    Returns: 73

  49. 22

    {277,897,38,750,983,427,503,204,113,149,307,722,885,466,282,258,314,548,442,596,478,555,174,288,251,981,162,366,29}

    Returns: 59

  50. 5

    {635,301,889,730,690,242,125,665,897,442,271,332,794,390,214,121,926,561,967,994,682,666,251,846,225,914,941,627}

    Returns: 169

  51. 33

    {747,570,558,561,197,653,122,420,410,140,895,940,707,309,503,919,954,3,653,40,585,967,9,338,510,100,662}

    Returns: 54

  52. 50

    {268,327,144,772,29,715,82,727,190,632,686,273,712,801,375,735,645,486,538,9,396,575,172,150,785,173,25,355,833,882,251}

    Returns: 62

  53. 41

    {61,206,663}

    Returns: 48

  54. 20

    {664,265,158,852,614,366,60}

    Returns: 52

  55. 38

    {366,57,391,621,485,806,752,826,702,502,971,434,675,730,658,969,867,311,463,610,456,376,206,265,463,757,529,322,471,743,502,566,56,882,482,482,430,135,151,748,884,805,335,491}

    Returns: 59

  56. 6

    {7 }

    Returns: 1

  57. 2

    {1, 2, 3, 1000 }

    Returns: 334

  58. 4

    {43, 81, 17, 1, 9 }

    Returns: 17

  59. 9

    {9 }

    Returns: 9

  60. 5

    {2, 2, 7, 10 }

    Returns: 5

  61. 2

    {1000 }

    Returns: 334

  62. 9

    {10 }

    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: