Statistics

Problem Statement for "SlimeXSlimesCity"

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

You are playing a game titled Slimes City. You are managing several towns in this game.

You have N towns in a region. For simplicity, they are named 0 through N-1. The population of town i is population[i].

You are going to merge these towns to form one big city. The procedure is as follows. While the number of towns is more than one, pick two different towns, i and j. Delete these two towns and form a new one, with a population equal to the sum of the populations of towns i and j. The name of the newly formed town will be i if i had a larger population than j, or j if j had a larger population than i. If both of the original towns had the same population, either name can be chosen.

When this process ends, one town remains. That town's name becomes the city's name. Return the number of different possible names for the resulting city.

Definition

Class:
SlimeXSlimesCity
Method:
merge
Parameters:
int[]
Returns:
int
Method signature:
int merge(int[] population)
(be sure your method is public)

Constraints

  • population will contain between 2 and 50 elements, inclusive.
  • Each element of population will be between 1 and 1,000,000,000, inclusive.

Examples

  1. {2, 3, 4}

    Returns: 2

    If towns 0 and 1 are merged first, the city's name will be 1. Otherwise the city's name will be 2. It is illustrated by the following image that shows the only three possible ways to merge the cities.

  2. {1, 2, 3}

    Returns: 2

    If town 2 is merged first (with town 0 or 1), the city's name will be 2. Otherwise, if towns 0 and 1 are merged first (to form a new town named 1, with a population of 3) and then the resulting town is merged with town 2, the city can be named either 1 or 2. It's not possible for the city to be named 0.

  3. {8,2,3,8}

    Returns: 2

    There may be multiple towns with the same population.

  4. {1000000000, 999999999, 999999998, 999999997}

    Returns: 3

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

    Returns: 1

  6. {1,1,1}

    Returns: 3

  7. {1,1}

    Returns: 2

  8. {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912}

    Returns: 1

  9. {536870912,268435456,134217728,67108864,33554432,16777216,8388608,4194304,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1}

    Returns: 1

  10. {8388608,1024,131072,4,268435456,4096,262144,65536,16384,67108864,33554432,16777216,8,2097152,128,1,32,32768,64,134217728,524288,4194304,2,512,8192,256,536870912,2048,1048576,16}

    Returns: 1

  11. {8388608,1024,131072,4,268435456,4096,262144,65536,16384,67108864,33554432,16777216,8,2097152,128,1,32,32768,64,134217728,524288,4194304,2,512,8192,256,536870912,2048,1048576,16,31053630,558490010,549284480,339007660,490637317,919639275,114667712,279564429,254418094,566351725,218125422,724033571,908038454,548245735,320625104,99884110,912249545,982895294,242429798,645592008}

    Returns: 26

  12. {1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489}

    Returns: 1

  13. {387420489,129140163,43046721,14348907,4782969,1594323,531441,177147,59049,19683,6561,2187,729,243,81,27,9,3,1}

    Returns: 1

  14. {1,129140163,177147,729,531441,1594323,387420489,19683,81,2187,59049,27,43046721,14348907,9,6561,3,243,4782969}

    Returns: 1

  15. {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}

    Returns: 1

  16. {1000000000,100000000,10000000,1000000,100000,10000,1000,100,10,1}

    Returns: 1

  17. {1,100,1000000000,10000000,10000,100000,1000000,10,1000,100000000}

    Returns: 1

  18. {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733}

    Returns: 44

  19. {701408733,433494437,267914296,165580141,102334155,63245986,39088169,24157817,14930352,9227465,5702887,3524578,2178309,1346269,832040,514229,317811,196418,121393,75025,46368,28657,17711,10946,6765,4181,2584,1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2,1,1}

    Returns: 44

  20. {8,21,39088169,377,6765,121393,89,433494437,10946,9227465,17711,233,2178309,1,2584,4181,832040,3524578,165580141,46368,1597,196418,267914296,55,2,987,514229,13,1346269,610,701408733,14930352,5702887,102334155,144,63245986,5,24157817,75025,1,34,28657,3,317811}

    Returns: 44

  21. {8,21,39088169,377,6765,121393,89,433494437,10946,9227465,17711,233,2178309,1,2584,4181,832040,3524578,165580141,46368,1597,196418,267914296,55,2,987,514229,13,1346269,610,701408733,14930352,5702887,102334155,144,63245986,5,24157817,75025,1,34,28657,3,317811,513865457,334567396,991752367,669518855,76239064,691943980}

    Returns: 50

  22. {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733}

    Returns: 44

  23. {701408733,433494437,267914296,165580141,102334155,63245986,39088169,24157817,14930352,9227465,5702887,3524578,2178309,1346269,832040,514229,317811,196418,121393,75025,46368,28657,17711,10946,6765,4181,2584,1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2,1,1}

    Returns: 44

  24. {63245986,24157817,267914296,89,1,9227465,610,233,121393,5,701408733,28657,196418,317811,2,17711,165580141,8,102334155,377,10946,34,39088169,514229,144,55,1597,46368,21,1,433494437,987,5702887,75025,1346269,2178309,832040,4181,3,14930352,6765,3524578,13,2584}

    Returns: 44

  25. {63245986,24157817,267914296,89,1,9227465,610,233,121393,5,701408733,28657,196418,317811,2,17711,165580141,8,102334155,377,10946,34,39088169,514229,144,55,1597,46368,21,1,433494437,987,5702887,75025,1346269,2178309,832040,4181,3,14930352,6765,3524578,13,2584,313766833,154668597,776539369,833674284,681101914,486651229}

    Returns: 50

  26. {1,1}

    Returns: 2

  27. {1000000000,1000000000}

    Returns: 2

  28. {1,1000000000}

    Returns: 1

  29. {1000000000,1}

    Returns: 1

  30. {1000000000,999999999}

    Returns: 1

  31. {1,2}

    Returns: 1

  32. {1,1000000000}

    Returns: 1

  33. {1000000000,1}

    Returns: 1

  34. {1,1000000000}

    Returns: 1

  35. {1000000000,1}

    Returns: 1

  36. {1,1,1}

    Returns: 3

  37. {1000000000,1000000000,1000000000}

    Returns: 3

  38. {1,1000000000,1}

    Returns: 1

  39. {1000000000,1,1000000000}

    Returns: 2

  40. {1000000000,999999999,1000000000}

    Returns: 2

  41. {1,2,1}

    Returns: 3

  42. {1,1,1000000000}

    Returns: 1

  43. {1,1000000000,1000000000}

    Returns: 2

  44. {1,500000000,1000000000}

    Returns: 1

  45. {1000000000,500000000,1}

    Returns: 1

  46. {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: 50

  47. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 50

  48. {1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000}

    Returns: 25

  49. {1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1}

    Returns: 25

  50. {1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999}

    Returns: 50

  51. {1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2}

    Returns: 50

  52. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1000000000,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

  53. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 49

  54. {1,20408164,40816327,61224490,81632653,102040817,122448980,142857143,163265306,183673470,204081633,224489796,244897959,265306123,285714286,306122449,326530612,346938776,367346939,387755102,408163265,428571429,448979592,469387755,489795918,510204082,530612245,551020408,571428571,591836735,612244898,632653061,653061224,673469388,693877551,714285714,734693877,755102041,775510204,795918367,816326530,836734694,857142857,877551020,897959183,918367347,938775510,959183673,979591836,1000000000}

    Returns: 48

  55. {1000000000,979591836,959183673,938775510,918367347,897959183,877551020,857142857,836734694,816326530,795918367,775510204,755102041,734693877,714285714,693877551,673469388,653061224,632653061,612244898,591836735,571428571,551020408,530612245,510204082,489795918,469387755,448979592,428571429,408163265,387755102,367346939,346938776,326530612,306122449,285714286,265306123,244897959,224489796,204081633,183673470,163265306,142857143,122448980,102040817,81632653,61224490,40816327,20408164,1}

    Returns: 48

  56. {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: 49

  57. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 49

  58. {1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1}

    Returns: 24

  59. {1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000,1,1000000000}

    Returns: 25

  60. {1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000}

    Returns: 49

  61. {1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1}

    Returns: 49

  62. {1,1,1000000000,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

  63. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 48

  64. {1,20833334,41666667,62500000,83333334,104166667,125000000,145833334,166666667,187500000,208333334,229166667,250000000,270833334,291666667,312500000,333333334,354166667,375000000,395833333,416666667,437500000,458333333,479166667,500000000,520833333,541666667,562500000,583333333,604166667,625000000,645833333,666666667,687500000,708333333,729166666,750000000,770833333,791666666,812500000,833333333,854166666,875000000,895833333,916666666,937500000,958333333,979166666,1000000000}

    Returns: 47

  65. {1000000000,979166666,958333333,937500000,916666666,895833333,875000000,854166666,833333333,812500000,791666666,770833333,750000000,729166666,708333333,687500000,666666667,645833333,625000000,604166667,583333333,562500000,541666667,520833333,500000000,479166667,458333333,437500000,416666667,395833333,375000000,354166667,333333334,312500000,291666667,270833334,250000000,229166667,208333334,187500000,166666667,145833334,125000000,104166667,83333334,62500000,41666667,20833334,1}

    Returns: 47

  66. {841336239,620727478,814959311,574428058,878600634,932761155,960659783,975952040,409973906,45329571,353136483,486727615,349871795,721443466,145439212}

    Returns: 13

  67. {699213626,326520684,538659617,390291053,104648769,427267085,495001258}

    Returns: 6

  68. {15797672,890046397,746767091,862163141,530615741,342288638,712659530,669562249,203613633,673003353,255376054}

    Returns: 9

  69. {879962143,922245539,519796107,553515719,482574737,991184939,641369173,970089740,726533284,711386624,858721939,814876593,977226706,600309397,3648768,438891247,279132791,808735852,753158965,818872270,682730565,523549621,311100421,609176320,770327945,19632793,683771136,465128151,684949225,36119998,91590246,524290824,918506074,265974968,516459051,369907654,322229406,414675998,327397337,261046036,308304432,792860624,968789609,449425989,646291895,93849323,731431762,438806717,20747139,723781306}

    Returns: 46

  70. {310090552,428269275}

    Returns: 1

  71. {182999827,720462573,554604024,609459944,709767990}

    Returns: 4

  72. {998024547,398128770,905355623,172239084,139060159,829752838,235165267,959324128,648563946,416408865,594362230}

    Returns: 10

  73. {952101495,738632240,999732509,176982976,358117725,810596742,134661646,66970225,995089962,425861775,867655553,147173266,632179513,254684471,907892011,189611115,901043546,717071738,177636384,495173561,568273061,779857080,846871058}

    Returns: 22

  74. {164542402,504203595,660684707,58067473,319374952,651515693,127505853,973695737,892427853,171250550,34376166,958796966,782929219,597992596,487360963,699022232,967463461,618840903,135402558,940492058,499313403,820868010,246697022,331089577,725909024,960682294,87175812,124948890,24680355,803318682,348931228,630555557,762071967,739057151,172414273,668605124,902543170,744617089,818262831,39040796,808122915,312476411,175952712,173850242,568455293,64444619,598458198,270624306,81482940}

    Returns: 48

  75. {1,2}

    Returns: 1

  76. {999999999,1000000000}

    Returns: 1

  77. {22898870,28370919}

    Returns: 1

  78. {979842486,924281383}

    Returns: 1

  79. {990235899,956631609}

    Returns: 1

  80. {103810833,746042109}

    Returns: 1

  81. {383622629,198416847}

    Returns: 1

  82. {2,2,2,2,1,1,1,1,1,1,2,1,2,1,1,1,1,2,1,2,2,1,1,2,2,1,2,2,1,2,2,1,1,2,1,2,1,1,2,2,1,2,2,2,2,1,1,2,2,2}

    Returns: 50

  83. {999999999,1000000000,999999999,999999999,999999999,999999999,1000000000,999999999,999999999,1000000000,999999999,1000000000,999999999,999999999,1000000000,999999999,1000000000,999999999,999999999,1000000000,1000000000,999999999,999999999,999999999,1000000000,999999999,999999999,999999999,999999999,1000000000,1000000000,1000000000,999999999,999999999,999999999,1000000000,1000000000,1000000000,1000000000,1000000000,999999999,1000000000,999999999,999999999,999999999,1000000000,1000000000,999999999,999999999,1000000000}

    Returns: 50

  84. {3203405,19390666,13588998,95853206,33340888,19169445,11462504,92869820,78252584,55414822,85893947,32606405,80965302,74898411,58126332,53893436,93944549,41269936,49683898,7193452,12599421,92718011,17111446,50953192,76482011,4296867,53352153,19714929,52107565,99709833,10753499,72999058,8680323,6842699,87763793,93129367,69560850,34605757,48562814,34370222,85447196,84860583,1182206,73537463,94936558,39118396,28727479,28233350,61483984,42345815}

    Returns: 49

  85. {906662371,940270940,927789731,980386883,954610753,931320406,972652868,928542979,948612133,971389960,916470103,991860225,959513152,907045225,905558141,919653915,959743574,950516854,906153900,911592143,952817642,975519726,910644727,991875359,949301315,919812879,907137272,932386995,960989299,985382129,975244367,992433879,993574859,909278314,943521730,997698687,922167925,973397500,994686411,941108086,960408693,953801202,992918851,961114847,912184771,981447075,979673826,982877253,984147204,999815262}

    Returns: 49

  86. {2621885,940260229,15540956,950122481,68367941,936444286,923065530,8699658,78750017,8571127,936550618,25507600,92725746,987987168,38038010,945983874,80172260,27913597,997061118,903901752,26224085,915477054,50797126,30114737,97371134,998959388,914440265,70047302,921013296,28217824,73704750,993022713,96997114,904977510,15756391,38246137,910879141,4537232,975117947,34445675,903156440,86185698,943267172,920826086,910552227,183998,24059831,931446732,941162910,910964234}

    Returns: 47

  87. {672465639,476008568,260387018,781099624,166425063,565092866,724909821,894442453,120378914,752433260,422897392,670675746,352618325,914601039,620868229,971038363,924858771,199161160,45156762,692844359,785087692,977901243,705155205,704959619,699675409,785032524,560928964,807677698,842121827,999822418,438805061,482916170,781460205,85390239,215293377,604012032,539595883,742123223,292244225,286119356,197761202,43252398,847261293,130416583,116120415,892806102,491949049,283370040,351409965,569591874}

    Returns: 49

  88. {493871736,439879501,47336771,350638979,142302189,62835625,851198683,281510579,532561933,474540907,882048209,431022028,578875109,74053630,844593964,107668317,274564019,917933917,923830547,390445073,603458041,261732253,120151499,236305837,815771642,984642370,132095000,768017385,879992254,625758783,294820015,462819645,286444186,685344591,853337564,134509121,637800850,696610285,97713165,700922816,462005053,52409334,489076385,756588651,920462898,657594354,5822051,638024616,933358832,167881765}

    Returns: 49

  89. {1, 2, 4, 6, 14, 16, 20}

    Returns: 3

  90. {1, 3, 5, 7, 8, 10, 21, 23, 45, 678, 3330, 4445, 5567, 6789, 9832, 278934, 4749874, 387383, 3873893, 3873, 378636, 3783, 38733, 38739, 393783, 38973, 3637, 37, 458579, 587585, 5857895, 587598, 5857985, 58759, 5857985, 5987589, 5985795, 5857895, 58579, 589579 }

    Returns: 16

  91. {1000000000, 999999999, 999999998, 9999997, 999999996, 999999995, 999999994, 999999993, 999999992, 999999991, 999999990, 999999989, 999999988, 999999987, 999999986, 999999985, 999999984, 999999983, 999999982, 999999981, 999999980, 999999979, 999999978, 999999977, 999999976, 999999975, 999999974, 999999973, 999999972, 999999971, 999999970, 999999969, 999999968, 999999967, 999999966, 999999965, 999999964, 999999963, 999999962, 999999961, 999999960, 959, 99958, 99999957, 999999956, 999999955, 999999954, 9999953, 999999952, 999999951 }

    Returns: 45

  92. {1, 1, 2, 10 }

    Returns: 1

  93. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999998, 999999998, 999999998, 999999998, 999999998, 999999998, 999999998, 999999998, 999999998, 999999997, 999999997, 999999997, 999999997, 999999997, 999999997, 999999997, 999999997, 999999997, 1 }

    Returns: 47

  94. {1, 3, 3, 7 }

    Returns: 3

  95. {1, 1, 1, 1, 4, 8 }

    Returns: 6

  96. {999999999, 999999999, 999999999, 1000000000 }

    Returns: 4

  97. {1000000000, 999999999, 999999998, 999999997 }

    Returns: 3

  98. {3, 1, 2, 5, 17, 10 }

    Returns: 5

  99. {53, 18479, 6346, 26512, 19181, 15736, 11490, 29370, 26974, 24476, 5717, 28157, 23293, 16839, 9973, 503, 3007, 11954, 4839, 5448, 32403, 14616, 3914, 165, 304, 12394, 17433, 18728, 19730, 19907, 5459, 21738, 14783, 11550, 1881, 19924, 25679, 26311, 17047, 9906, 28715, 23823, 31334, 30345, 17685, 4676, 15153, 7723, 28265, 6880 }

    Returns: 45

  100. {5, 4, 5, 3, 7, 88, 6, 4, 345757, 1000000000, 1000000000 }

    Returns: 2

  101. {1, 2, 4, 8, 14, 16, 20 }

    Returns: 4

  102. {4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1 }

    Returns: 50

  103. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 7

  104. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 49

  105. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 50

  106. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 999999999, 1 }

    Returns: 49

  107. {1, 1, 1, 1, 2 }

    Returns: 5

  108. {2, 2, 2, 6 }

    Returns: 4

  109. {1, 49, 50, 100 }

    Returns: 3

  110. {1, 1, 2, 4, 8 }

    Returns: 5

  111. {1, 1, 1, 1, 1, 2 }

    Returns: 6

  112. {1000000000, 999999999, 999999998, 999999997, 999999996, 999999999, 999999999, 888888888, 888888888, 888888888, 888888888, 888888888, 888888888, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999 }

    Returns: 21

  113. {23, 11, 10, 9 }

    Returns: 3

  114. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 100000079, 1000000000, 1000000000 }

    Returns: 49

  115. {1, 2, 3, 4, 5, 2, 2, 8, 8, 8, 5 }

    Returns: 10

  116. {1, 1, 8, 11 }

    Returns: 1

  117. {2, 2, 2, 4 }

    Returns: 4

  118. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 936870912, 936870913, 936870914, 936870915, 936870916, 134217728, 268435456, 536870912, 936870912, 936870913, 936870914, 936870915, 936870916 }

    Returns: 16

  119. {1, 3, 3, 3, 9 }

    Returns: 4

  120. {2, 2, 4, 6, 12, 16, 20 }

    Returns: 7

  121. {2726, 6298, 10619, 14672, 10838, 32232, 14008, 15202, 769, 17024, 15198, 31583, 2429, 19187, 143, 31090, 27289, 18660, 2351, 9595, 11521, 25951, 25322, 31752, 10849, 25964, 2168, 28545, 9165, 31971, 14623, 29090, 30049, 17281, 27002, 12590, 11556, 60, 12666, 24546, 2354, 16084, 23466, 5288, 8475, 25515, 31159, 7694, 16006, 12758 }

    Returns: 47

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

    Returns: 6

  123. {1, 1, 2, 4, 8, 16 }

    Returns: 6

  124. {2, 2, 3 }

    Returns: 3

  125. {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: 48

  126. {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: 50

  127. {1, 1, 1, 3 }

    Returns: 4

  128. {1, 2, 3, 5 }

    Returns: 3

  129. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 21

  130. {1, 1, 1, 1, 1, 5, 1, 1 }

    Returns: 8

  131. {9, 9, 15, 20 }

    Returns: 4

  132. {76, 67, 756, 6, 4353, 54, 67, 6, 56, 5, 5, 4, 4, 4, 3, 4, 4, 4, 4, 4, 5, 5 }

    Returns: 1

  133. {999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 90, 999999999, 999999999, 99, 909845, 580, 999999999, 999999999, 4, 999999999 }

    Returns: 11

  134. {1361915, 207572679, 628126348, 376128985, 883488319, 186963881, 762865355, 326392579, 98149108, 158171746, 61370502, 127856988, 9580347, 570852624, 646119602, 178503576, 484012896, 61261436, 841056889, 558195740, 940535013, 26358308, 579095856, 496132859, 925772920, 837126194, 70268512, 656565239, 285836283, 902043522, 403561408, 727101573, 9467003, 296222623, 631246137, 899346888, 520674360, 798547141, 491732704, 799288980, 643196067, 789180383, 614589693, 162728299, 456503386, 555236488, 806931466, 181452418, 528140589, 751331085 }

    Returns: 46

  135. {16, 8, 4, 2, 1 }

    Returns: 1

  136. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 999999999, 99999991, 3 }

    Returns: 8

  137. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 9, 5, 5, 56, 5, 5, 5, 54, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    Returns: 49

  138. {1, 1, 4 }

    Returns: 1

  139. {1, 1, 1, 2, 4 }

    Returns: 5

  140. {6, 3, 2, 2 }

    Returns: 4

  141. {1000000000, 999999999, 999999998, 999999997, 212121, 233232, 232323, 211221, 1, 2, 3, 4, 5, 6, 8, 9, 3, 3, 2, 22121, 3325, 5445, 6656, 5775, 4242, 24442, 2332, 88686, 6866, 333, 55353 }

    Returns: 4

  142. {1, 3, 7 }

    Returns: 1

  143. {67687, 2314, 234, 5435, 67, 23, 6575, 89, 32, 645, 345, 85, 324, 575, 234, 6785, 234, 76, 2364, 658, 3442, 964, 780, 4353, 645, 242, 5464, 2334, 453, 45645, 324532, 675, 3453, 756, 23452, 675, 2534, 5645, 312, 645, 342, 3245, 675, 324, 64, 432, 987, 654, 234 }

    Returns: 1

  144. {1, 1, 2 }

    Returns: 3

  145. {3, 2, 5, 9 }

    Returns: 3

  146. {1, 2, 3, 4, 5, 6 }

    Returns: 5

  147. {1, 1, 2, 3 }

    Returns: 4

  148. {1, 5, 5, 11 }

    Returns: 3

  149. {200, 300, 400, 800 }

    Returns: 3

  150. {999999949, 999999950, 999999951, 999999952, 999999953, 999999954, 999999955, 999999956, 999999957, 999999958, 999999959, 999999960, 999999961, 999999962, 999999963, 999999964, 999999965, 999999966, 999999967, 999999968, 999999969, 999999970, 999999971, 999999972, 999999973, 999999974, 999999975, 999999976, 999999977, 999999978, 999999979, 999999980, 999999981, 999999982, 999999983, 999999984, 999999985, 999999986, 999999987, 999999988, 999999989, 999999990, 999999991, 999999992, 999999993, 999999994, 999999995, 999999996, 999999997, 999999998 }

    Returns: 49

  151. {1000000000, 1000000000, 1000000000, 999999999, 999999999, 999999999 }

    Returns: 6

  152. {8468, 6335, 6501, 9170, 5725, 1479, 9359, 6963, 4465, 5706, 8146, 3282, 6828, 9962, 492, 2996, 1943, 4828, 5437, 2392, 4605, 3903, 154, 293, 2383, 7422, 8717, 9719, 9896, 5448, 1727, 4772, 1539, 1870, 9913, 5668, 6300, 7036, 9895, 8704, 3812, 1323, 334 }

    Returns: 39

  153. {2, 2, 3, 5 }

    Returns: 4

  154. {2, 2 }

    Returns: 2

  155. {5, 5, 10 }

    Returns: 3

  156. {1, 1 }

    Returns: 2

  157. {499999999, 499999999, 499999999, 499999999, 1000000000 }

    Returns: 5

  158. {1, 5, 5, 10 }

    Returns: 3

  159. {1, 1, 1, 3, 3, 3, 3, 15 }

    Returns: 8

  160. {1000000000, 999999999, 999999998, 999999997, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999, 99999999 }

    Returns: 29

  161. {1, 1, 1, 1, 1, 1, 3, 7 }

    Returns: 8

  162. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

    Returns: 14

  163. {2, 3, 5, 10 }

    Returns: 3

  164. {3, 3, 3, 3, 3, 10 }

    Returns: 6

  165. {1000000000, 999999999, 999999998, 999999997, 999999996, 999999995, 999999997, 999999993, 999999991, 999999999, 999999998, 999999997, 999999990, 999999999, 999999998, 999999997, 999999998, 999999997, 9999991, 9999999, 999999998, 999999997, 99990, 999999999, 999999998, 1000000000, 999999999, 999999998, 999999997, 999999996, 999999995, 999999997, 999999993, 999999991, 999999999, 999999998, 999999997, 999999990, 999999999, 999999998, 999999997, 999999998, 999999997, 9999991, 9999999, 999999998, 999999997, 99990, 999999999, 999999998 }

    Returns: 44

  166. {12, 15, 21, 23, 10, 14, 15, 18, 19, 21, 20, 17, 16, 14, 13, 8, 9, 23, 27, 29, 32, 27, 25, 14, 13, 13, 12, 11, 10, 9, 7, 6, 16, 15, 24, 26, 21, 22, 19, 16, 17, 26, 25, 29, 26, 21, 20, 10 }

    Returns: 47

  167. {5, 4, 5, 3, 7, 88, 6, 4, 345757, 1000000000, 1000000000, 123535, 35235235, 23523535 }

    Returns: 2

  168. {1, 1, 2, 2, 3, 3 }

    Returns: 6

  169. {5, 5, 5, 10, 10, 20 }

    Returns: 6

  170. {1, 1, 1, 3, 4 }

    Returns: 5

  171. {2, 3, 4, 6 }

    Returns: 3

  172. {1, 2, 3, 4, 10 }

    Returns: 4

  173. {2, 3, 4, 7 }

    Returns: 3

  174. {3, 4, 5, 9 }

    Returns: 3

  175. {2, 4, 6, 10 }

    Returns: 3

  176. {10, 10, 20 }

    Returns: 3

  177. {10, 10, 10, 30 }

    Returns: 4

  178. {1, 1, 1, 1, 1, 5 }

    Returns: 6

  179. {1, 2, 3, 4 }

    Returns: 3

  180. {4, 5, 6, 12 }

    Returns: 3

  181. {10000000, 232, 444, 4442, 123, 1, 2, 666, 6, 1, 10000000, 232, 444, 4442, 123, 1, 2, 666, 6, 1, 10000000, 232, 444, 4442, 123, 1, 2, 666, 6, 1, 10000000, 232, 444, 4442, 123, 1, 2, 666, 6, 1, 10000000, 232, 444, 4442, 123, 1, 2, 666, 6, 1 }

    Returns: 5

  182. {3, 2, 1, 1 }

    Returns: 4

  183. {5, 5, 5, 10, 25 }

    Returns: 5

  184. {10, 10, 20, 40 }

    Returns: 4

  185. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

    Returns: 10

  186. {5, 5, 10, 20 }

    Returns: 4

  187. {10, 11, 12, 25 }

    Returns: 3

  188. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 936870912, 936870913, 936870914, 936870915, 936870916, 134217728, 268435456, 536870912, 936870912, 936870913, 936870914, 936870915, 936870916, 936870913, 936870914, 936870915, 936870216 }

    Returns: 20

  189. {10, 1, 2, 3, 4 }

    Returns: 4

  190. {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, 999999991, 999999992, 999999993, 999999994, 999999995, 999999996, 999999997, 999999998, 999999999, 999999990, 999999991, 999999992, 999999993, 999999994, 999999995, 999999996, 999999997, 999999998, 999999999, 999999980, 999999981, 999999982, 999999983, 999999984, 999999985 }

    Returns: 25

  191. {1, 1, 1, 1, 1, 5, 10 }

    Returns: 7

  192. {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 20 }

    Returns: 12

  193. {1, 2, 3, 6 }

    Returns: 3

  194. {2, 2, 3, 3, 7 }

    Returns: 5

  195. {2, 3, 4, 5, 6 }

    Returns: 4

  196. {999, 1000, 1999, 3998 }

    Returns: 3

  197. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 100 }

    Returns: 1

  198. {2, 4, 6, 12 }

    Returns: 3

  199. {1, 10000 }

    Returns: 1

  200. {1, 1, 1, 1, 1, 6 }

    Returns: 1

  201. {1, 2 }

    Returns: 1

  202. {1, 1, 1, 2, 5 }

    Returns: 5

  203. {3, 4, 5, 10 }

    Returns: 3

  204. {1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 }

    Returns: 11

  205. {67, 89, 45, 67, 45, 7, 6, 4, 67887, 5676, 34546, 34465, 456, 565, 567, 5767, 456, 765, 56575, 656, 57, 56, 5, 7, 567, 54, 6, 6, 56, 56, 5, 765, 6, 567, 5, 65, 6, 57, 56, 5, 65, 56, 56, 5, 65, 6, 56, 5, 65, 57 }

    Returns: 4

  206. {999999998, 999999999, 999999999, 999999999, 1000000000 }

    Returns: 4

  207. {1, 1, 3, 4 }

    Returns: 2

  208. {2, 2, 4, 8 }

    Returns: 4

  209. {5, 7, 8, 15 }

    Returns: 3

  210. {1, 1000000000 }

    Returns: 1

  211. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 10, 13, 14, 15, 16, 17, 1, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 341, 32, 33, 34, 35, 36, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500 }

    Returns: 50

  212. {1000000000, 1000000000, 100008000, 190000000, 999999999, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 100000079, 1000000000, 1000000000 }

    Returns: 47

  213. {1, 1, 2, 4, 8, 16, 32, 65, 129, 65, 257, 513 }

    Returns: 5

  214. {100, 100, 5, 4, 3, 100, 85, 15, 15, 7, 85, 3, 15 }

    Returns: 5

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: