Statistics

Problem Statement for "Cryptography"

Problem Statement

TopCoder Security Agency (TSA, established today) has just invented a new encryption system! This encryption system takes as its input a list of numbers to encrypt.

You work at TSA and your task is to implement a very important part of the encryption process. You are allowed to pick one number in the input list and increment its value by 1. This should be done in such way that the product of all numbers in the list after this change becomes as large as possible.

Given the list of numbers as int[] numbers, return the maximum product you can obtain. It is guaranteed that the return value will not exceed 2^62.

Definition

Class:
Cryptography
Method:
encrypt
Parameters:
int[]
Returns:
long
Method signature:
long encrypt(int[] numbers)
(be sure your method is public)

Constraints

  • numbers will contain between 2 and 50 elements, inclusive.
  • Each element of numbers will be between 1 and 1000, inclusive.
  • The return value will not exceed 2^62.

Examples

  1. {1,2,3}

    Returns: 12

    If we increment the first number, we get 2*2*3 = 12. If we increment the second, we get 1*3*3 = 9. If we increment the third, we get 1*2*4 = 8. Hence, the correct return value is 12.

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

    Returns: 36

    The elements of numbers are not necessarily unique.

  3. {1000,999,998,997,996,995}

    Returns: 986074810223904000

    The answer may be very big, but will not exceed 2^62.

  4. {1,1,1,1}

    Returns: 2

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

    Returns: 2615348736000

  6. {1,3}

    Returns: 6

  7. {1,3,3}

    Returns: 18

  8. {6,3,2,3,2}

    Returns: 324

  9. {7,4,1,2,1,1,3,2}

    Returns: 672

  10. {5,1,2,2,6,5,1,3,2,2,1,3}

    Returns: 43200

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

    Returns: 518400

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

    Returns: 1866240

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

    Returns: 21767823360

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

    Returns: 2476694568960

  15. {3,1,1,1,4,3,2,4,1,1,3,3,3,2,2,1,3,2,6,2,5,4,1,3,3,6,2,3,6,3,5,7,3,7,2,2,1,1,1,1,4,3,5,3,4,1,3}

    Returns: 3317625251168256000

  16. {1,3,2,2,3,2,3,1,3,1,3,1,2,4,4,1,4,1,2,4,2,1,2,3,2,3,3,4,1,1,6,3,2,1,1,3,2,3,3,1,4,3,9,3,1,3,2,2,7,5}

    Returns: 909977211749007360

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

    Returns: 1232561725966909440

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

    Returns: 770351078729318400

  19. {5,1,4}

    Returns: 40

  20. {10,1,5,1,2,1,1,6}

    Returns: 1200

  21. {1,3,7,2,1,2,1,21,8,4,4,3,6,4,8,3}

    Returns: 780337152

  22. {6,3,4,4,2,8,1,8,2,5,2,1,8,2,3,1,2,3,2,3,3,11,1,4,4,2,5,3,4}

    Returns: 161443794124800

  23. {2,2,1,3,4,6,1,1,3,3,1,2,7,2,2,1,5,4,1,1,3,7,3,2,7,11,1,1,1,7,1,5,8,1,1,1,7,3,3,3,1,2,1,6,3,11,2}

    Returns: 2360963662538342400

  24. {4,2,4,2,1,1,4,7,1,3,2,1,3,5,2,2,2,1,5,5,2,1,3,4,5,6,1,1,2,6,2,3,1,3,9,6,3,2,1,1,5,2,3,5,1,1,1,1,3,2}

    Returns: 2925595459584000000

  25. {881,848,22,759,686,235,855}

    Returns: 1797626514935512800

  26. {800,308,172,89,542,109,602}

    Returns: 135654415852032000

  27. {935,836,971,516,885,844}

    Returns: 293098353412642800

  28. {684,873,18,422,236,163,185,56}

    Returns: 1908076400504628480

  29. {147,731,181,103,90,229,791}

    Returns: 33022037742265299

  30. {498,538,210,485,211,450,834}

    Returns: 2171185010538282000

  31. {210,538,834,498,450,485,211}

    Returns: 2171185010538282000

  32. {485,538,211,210,834,498,450}

    Returns: 2171185010538282000

  33. {485,210,498,538,211,450,834}

    Returns: 2171185010538282000

  34. {485,210,450,834,211,538,498}

    Returns: 2171185010538282000

  35. {485,498,538,210,450,211,834}

    Returns: 2171185010538282000

  36. {688,794,325,116,283,232,840}

    Returns: 1145597005792512000

  37. {116,840,232,283,794,688,325}

    Returns: 1145597005792512000

  38. {232,840,794,325,116,283,688}

    Returns: 1145597005792512000

  39. {325,688,232,116,794,840,2,283}

    Returns: 3407416735177728000

  40. {325,840,688,794,232,2,283,116}

    Returns: 3407416735177728000

  41. {840,232,2,688,283,794,325,116}

    Returns: 3407416735177728000

  42. {2,2,2,2,2, 2,2,2,2,1, 1,1,1,1,1, 1,2,2,2,2, 1,2,1,1,1, 2,2,1,1,1, 2,2,1,1,2, 1,1,1,1,2, 1,1,1,2,1, 2,1,2,1,2}

    Returns: 33554432

  43. {2,1,2,3,3, 3,2,2,2, 3,2,3,2, 2,3,2, 3,3,3, 1,2,3,2, 2,2,2, 2,3,1,2,3, 1,3,3,3, 2,3,3,3, 3,2, 3,2, 3,3,3,2, 2,2,3}

    Returns: 2369190669160808448

  44. {4,5,3,1,4,3,3,5,3,5,1,4,4,5,5,4,1,4,1,4,3,5,1,4,3,4,1,1,2,4,5,4,1,4,3,2,5,5,2,3}

    Returns: 3439853568000000000

  45. {6,4,2,4,1,7,6,4,7,6,5,4,7,6,5,1,6,4,3,3,7,5,3,6,2,5,2,4,2,1,4}

    Returns: 991090610012160000

  46. {10,8,10,7,5,1,8,12,12,4,10,5,3,4,11,2,5,2,7,2,2,8,6,8,2}

    Returns: 732476473344000000

  47. {5,9,16,16,6,18,6,10,8,6,4,7,3,12,7,2,16,10,18,7,1}

    Returns: 2038814969167872000

  48. {21,20,14,9,14,5,9,16,13,5,10,3,25,6,11,4,4,18,2}

    Returns: 1482902733312000000

  49. {1,30,23,5,13,9,11,23,26,5,21,10,35,22,37,6}

    Returns: 953151246847800000

  50. {46,11,19,29,9,14,20,30,37,47,10,16,29}

    Returns: 188972654787840000

  51. {70,67,43,28,75,11,47,44,86,57,15}

    Returns: 772781896323360000

  52. {202,29,135,196,166,258,196,141}

    Returns: 189786554765740800

  53. {600,10,431,203,138,156,633}

    Returns: 7869092282251200

  54. {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: 1688849860263936

  55. {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3}

    Returns: 1801135623563989452

  56. {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,5}

    Returns: 1788139343261718750

  57. {8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8}

    Returns: 1297036692682702848

  58. {12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12}

    Returns: 2403495365635473408

  59. {19,19,19,19,19,19,19,19,19,19,19,19,19,19}

    Returns: 841059669245141180

  60. {25,25,25,25,25,25,25,25,25,25,25,25,25}

    Returns: 1549720764160156250

  61. {37,37,37,37,37,37,37,37,37,37,37}

    Returns: 182726206151878262

  62. {50,50,50,50,50,50,50,50,50,50}

    Returns: 99609375000000000

  63. {100,100,100,100,100,100,100,100,100}

    Returns: 1010000000000000000

  64. {275,275,275,275,275,275,275}

    Returns: 119372762695312500

  65. {777,777,777,777,777,777}

    Returns: 220335609371317146

  66. {1,2,2,2,2, 1,1,1,2,2, 1,2,2,1,1, 1,2,2,1,1, 2,2,2,1,2, 2,1,2,1,2, 2,1,2,1,2, 2,2,2,1,1, 1,1,1,2,2, 2,1,1,2,2}

    Returns: 536870912

  67. {2,2,3,3,3,3,2,2,2,3,3,2,3,3,2,3,3,2,2,3,3,2,3,3,3,3,2,3,3,3,3,3,2,3,2,2,2,2,2,3,2,2,3,2,2,2}

    Returns: 1776893001870606336

  68. {4,4,5,5,4,4,5,4,5,4,4,5,5,5,5,4,5,5,5,4,5,4,5,4,4,5,5,5}

    Returns: 3200000000000000000

  69. {8,8,8,7,7,7,8,8,7,7,8,8,7,7,8,7,7,8,7,8,8}

    Returns: 2773078757450186752

  70. {12,12,12,13,11,12,12,12,12,12,12,13,13,10,11,10,13}

    Returns: 1961474557091512320

  71. {18,19,17,19,19,19,20,20,20,20,17,19,18,18}

    Returns: 707012234657280000

  72. {24,25,23,26,23,27,22,23,26,26,23,24,22}

    Returns: 967627407648844800

  73. {33,35,33,33,38,38,36,35,39,38,33,38}

    Returns: 4381858202613091200

  74. {52,46,49,48,51,50,52,47,46,47,50}

    Returns: 3872626339196160000

  75. {102,94,94,105,91,90,94,99,94}

    Returns: 685518002684555040

  76. {290,256,277,274,293,247,256}

    Returns: 104815995052359680

  77. {806,842,781,781,755,813}

    Returns: 254426030465823216

  78. {904,966,923,965,994,965}

    Returns: 746910247147018500

  79. {3,784,7,9,19,12,354,155}

    Returns: 2471646804480

  80. {37,49,176,570,11,20,2,202}

    Returns: 24248262931200

  81. {11,109,3,86,24,59,10,271,16,2,18,7,112}

    Returns: 804083663078277120

  82. {115,121,12,28,141,4,25,25,100,30,320}

    Returns: 1977711120000000000

  83. {101,11,59,3,178,33}

    Returns: 1540139304

  84. {205,2,360,3,108,7}

    Returns: 502135200

  85. {179,64,132,117,178,10,94,228,409}

    Returns: 3036627313075040256

  86. {517,167,312,442,237,10,736,178}

    Returns: 4066518247440270336

  87. {210,22,775,69,4,9}

    Returns: 11117452500

  88. {265,954,10,23,116,4}

    Returns: 33724854000

  89. {7,884,73,23}

    Returns: 11873888

  90. {48,3,162,11,46}

    Returns: 15738624

  91. {259,505,272,33,879,108,138,279}

    Returns: 4421146270930986240

  92. {303,277,5,110,7,91,294,356,948}

    Returns: 3501155751995341440

  93. {499,429,22,473,498,86,274,161}

    Returns: 4399983495341762328

  94. {302,135,9,216,406,494,500,216}

    Returns: 1907529225638400000

  95. {93,17,717,75,16,48,197,628,213}

    Returns: 1828133559107899200

  96. {670,339,21,54,82,439,64,264,24}

    Returns: 3938804784057876480

  97. {10,51,19,4,88,5,16,11,36,207,132,593}

    Returns: 2188570779495936000

  98. {10,103,43,592,5,378,33,48,198}

    Returns: 18650513977159680

  99. {206,12,85}

    Returns: 227630

  100. {8,65,841}

    Returns: 491985

  101. {139,2,92}

    Returns: 38364

  102. {6,400,62}

    Returns: 173600

  103. {22,8,171}

    Returns: 33858

  104. {28,2,310}

    Returns: 26040

  105. {19,538}

    Returns: 10760

  106. {9,840}

    Returns: 8400

  107. {688,19}

    Returns: 13760

  108. {538,3,13}

    Returns: 27976

  109. {10,671}

    Returns: 7381

  110. {974,3}

    Returns: 3896

  111. {13,239}

    Returns: 3346

  112. {247,18}

    Returns: 4693

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

    Returns: 27021597764222976

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

    Returns: 27021597764222976

  115. {9,243,729,27,729,729,729,81}

    Returns: 1500946352969991210

  116. {9,27,81,243,729,729,729,729}

    Returns: 1500946352969991210

  117. {64,4,256,256,256,256,16,256,256}

    Returns: 1441151880758558720

  118. {4,16,64,256,256,256,256,256,256}

    Returns: 1441151880758558720

  119. {625,125,625,5,625,625,25,625}

    Returns: 1788139343261718750

  120. {5,25,125,625,625,625,625,625}

    Returns: 1788139343261718750

  121. {16,2,16,16,16,16,16,16,16,16,16,16,16,1,16,16,16}

    Returns: 4611686018427387904

  122. {1,1,1,1,16,16,16,1,1,1,2,1,16,1,16,1,16,16,1,1,1,16,1,1,16,1,1,1,16,1,1,16,1,16,1,1,1,16,1,16,1,1,1,16,1,1,1,1,1,1}

    Returns: 4611686018427387904

  123. {1, 1, 1, 1 }

    Returns: 2

  124. {1000, 999, 998, 997, 996, 995 }

    Returns: 986074810223904000

  125. {3, 2, 1 }

    Returns: 12

  126. {4, 3 }

    Returns: 16

  127. {17, 21, 3, 1, 5, 2 }

    Returns: 21420

  128. {3, 2, 2, 3 }

    Returns: 54

  129. {100, 100, 100, 100, 100, 100 }

    Returns: 1010000000000

  130. {1, 2, 3, 4, 5 }

    Returns: 240

  131. {1, 3, 2, 1, 1, 3 }

    Returns: 36

  132. {1000, 1000 }

    Returns: 1001000

  133. {99, 100 }

    Returns: 10000

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: