Statistics

Problem Statement for "IndependentOfOR"

Problem Statement

Let S be a set containing k non-negative integers: { S[0], ..., S[k-1] }. We define OR(S) to be the bitwise "or" of all elements of S. Formally: OR(S) = S[0] or S[1] or ... or S[k-1]. For consistency, if S is the empty set, then OR(S) is defined to be 0.

A set T is called "independent with respect to OR" if no two subsets of T produce the same value when OR is applied to them. Formally, T should have the following property: | { OR(S) : S is a subset of T } | = 2^|T|. In words: the set of all values OR(S), where S is a subset of T, contains exactly (2 to the size of T) distinct values.

You are given a int[] A that describes a set of integers. Your goal is to select a subset B of the set described by A. The subset B has to be independent with respect to OR, and the sum of its elements has to be as large as possible. Return the largest possible sum of elements of the set B.

Definition

Class:
IndependentOfOR
Method:
maxSum
Parameters:
int[]
Returns:
int
Method signature:
int maxSum(int[] A)
(be sure your method is public)

Constraints

  • A will contain between 1 and 50 elements, inclusive.
  • All elements of A will be pairwise distinct.
  • Each element in A will be between 1 and 1,000,000, inclusive.

Examples

  1. {2, 3}

    Returns: 3

    The optimal solution is: {3}. Note that {2, 3} is not a valid solution, since |OR({2, 3})| = |{0, 2, 3}| = 3 < 2^2 = 4.

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

    Returns: 11

    This time the optimal solution is {5, 6}.

  3. {2, 3, 5, 7, 11, 13, 17, 19}

    Returns: 41

  4. {8, 9, 13, 45, 47, 111, 127}

    Returns: 127

  5. {5, 8, 55, 58, 85, 88, 555, 558, 585, 588, 855, 858, 885, 888}

    Returns: 2919

  6. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288}

    Returns: 1048575

  7. {32, 544, 546, 802, 1826, 1954, 4002, 4006, 4070, 4071, 4087, 4095}

    Returns: 4095

  8. {2, 10, 522, 586, 602, 730, 734, 990, 991, 1023}

    Returns: 1023

  9. {1, 33, 41, 43, 47, 63, 127}

    Returns: 127

  10. {131072, 135168, 143360, 143872, 143880, 406024, 422408, 422536, 422792, 488328, 488344, 521112, 523160, 523224, 524248, 524249, 524253, 524255, 524287}

    Returns: 524287

  11. {16, 24, 28, 30, 31}

    Returns: 31

  12. {256, 260, 292, 33060, 98596, 98724, 98725, 100773, 100775, 100783, 101807, 101823, 110015, 114111, 130495, 131007, 131071}

    Returns: 131071

  13. {8, 24, 152, 184, 188, 252, 764, 1020, 1022, 2046, 2047}

    Returns: 2047

  14. {256, 288, 289, 353, 481, 483, 499, 1523, 1531, 3579, 4091, 4095}

    Returns: 4095

  15. {1, 1025, 1041, 9233, 9237, 9365, 13461, 13469, 15517, 31901, 31903, 31967, 31999, 32255, 32767}

    Returns: 32767

  16. {1, 65, 193, 195, 203, 235, 251, 255}

    Returns: 255

  17. {128, 132, 196, 197, 229, 237, 239, 255}

    Returns: 255

  18. {8, 10, 14, 30, 31}

    Returns: 31

  19. {256, 65792, 65824, 66336, 82720, 82724, 86820, 87844, 87852, 87854, 89902, 122670, 122798, 122862, 131054, 131055, 131071}

    Returns: 131071

  20. {2, 3, 35, 43, 47, 63}

    Returns: 63

  21. {4, 20, 28, 29, 31}

    Returns: 31

  22. {65536, 65600, 65602, 65606, 66118, 66134, 67158, 75350, 77398, 81494, 97878, 98006, 98038, 98039, 98047, 98303, 131071}

    Returns: 131071

  23. {4, 20, 84, 85, 93, 221, 253, 509, 511}

    Returns: 511

  24. {512, 516, 517, 773, 805, 813, 829, 831, 959, 1023, 2047}

    Returns: 2047

  25. {16, 80, 84, 86, 94, 95, 127}

    Returns: 127

  26. {32, 48, 112, 368, 496, 497, 501, 503, 511}

    Returns: 511

  27. {178, 62, 553, 371, 97, 490, 122, 195, 603, 440, 213, 687, 103, 411, 414, 150, 132, 23, 324, 366, 625, 486, 479}

    Returns: 1807

  28. {66, 316, 163, 309, 82, 51, 512, 534, 383, 562, 493, 535, 46, 536, 308, 182, 97, 223, 218, 632, 38, 652, 538}

    Returns: 2162

  29. {20213, 7323, 25746, 22018, 10878, 4828, 2386, 15395, 22256, 14232, 23894, 25895, 3672, 6520, 1963, 7670, 2648, 5294, 23767, 26726, 8611, 22120, 14176, 26025, 29291, 477, 14419, 11100}

    Returns: 115079

  30. {27922, 16377, 26596, 47630, 14192, 9579, 17656, 40346, 36512, 31406, 41456, 7552, 36725, 9263, 8978, 46337, 15805, 2096, 42335, 42855, 39982, 35729, 36635, 21484, 19358, 21911, 40365, 3851, 7437}

    Returns: 202217

  31. {338, 139, 4, 387, 87, 231, 233, 295, 507, 90, 523, 174, 467, 336, 425, 161, 232, 490, 173, 112, 404, 303, 369, 162, 532, 262, 365, 170, 317, 171, 153, 55, 256, 284, 424, 70, 444, 208, 458, 62}

    Returns: 1937

  32. {1580, 3789, 2513, 1146, 2255, 774, 2621, 4060, 3325, 1030, 4018, 1853, 2019, 4056, 3720, 5145, 4865, 1492, 2420, 607, 3218, 4821, 4554, 3774, 4266, 2758, 2324, 3528, 3617, 588, 3179, 544, 3207, 4634, 2072}

    Returns: 23069

  33. {40891, 37952, 39102, 2044, 59439, 15090, 32574, 2206, 36293, 8208, 37658, 4166, 46709, 15722, 17817, 10739, 14047, 9641, 50110, 10849, 60283, 23241, 53578}

    Returns: 213312

  34. {37, 16, 32, 28, 34, 48, 42, 17, 20}

    Returns: 127

  35. {347, 214, 95, 567, 366, 462, 50, 539, 69, 540, 503, 32, 601, 492, 373, 48, 306, 544, 137, 446, 481, 175, 459, 432, 136, 565, 122, 557, 127, 35, 536, 369, 585, 1, 183, 580, 444, 161, 618, 176, 656, 611, 767, 107, 18, 586}

    Returns: 2967

  36. {1721, 1616, 4588, 6061, 4492, 4090, 5684, 5442, 3759, 3957, 949, 2800, 492, 1828, 3069, 4374}

    Returns: 18395

  37. {3553, 660, 3403, 459, 431, 1630, 3673, 3669, 3934, 3170, 2141, 248, 48, 2549, 1596, 2287}

    Returns: 14065

  38. {15984, 13373, 72865, 27307, 44595, 47184, 20758, 16176, 45506, 22300, 39520, 62387, 28655, 66628, 69839, 9060, 8449, 8436, 29110, 48810, 22114, 8787, 58658, 53990, 57013, 35184, 58671, 8157, 57057, 34051, 48227, 68862, 67925, 7600, 50380, 22854, 30593, 52836, 21138, 42119, 29603, 14023, 18892, 61739, 2891, 61989, 26995, 52307, 4694, 10407}

    Returns: 343974

  39. {17, 24, 18, 10, 20, 6, 13, 30, 3, 27, 8, 21, 32, 16, 33, 19, 25, 5, 11, 22, 23, 14, 15, 29, 26, 9, 4}

    Returns: 111

  40. {544357, 431924, 410189, 238737, 5780, 514322, 168267, 9410, 592353, 159892, 406479, 375016, 93021, 241853, 519611, 280012, 515734, 414290, 37541}

    Returns: 2171892

  41. {54, 75, 153, 175, 69, 149, 135, 99, 41, 9, 171}

    Returns: 534

  42. {161624, 24647, 48258, 143054, 151942, 225535, 193561, 20256, 3417, 112623, 173678, 11440, 54380, 192741, 60387, 101668, 98563, 223817, 50994, 31670, 7602}

    Returns: 804537

  43. {1, 7, 21, 56, 78, 38, 4, 5, 20, 50, 37, 58, 34, 80, 41, 60, 61, 72, 74, 45, 32, 77, 48, 31, 65, 42, 44, 33, 73, 6, 10, 70, 43, 30, 27}

    Returns: 323

  44. {1433, 1259, 3087}

    Returns: 5779

  45. {165, 222, 179, 67, 249, 215, 228, 188, 86, 185, 72, 130, 124, 120, 56, 21, 155, 24, 109, 30, 181, 149, 210, 233, 147, 137, 93, 153, 27, 126, 94, 115, 194, 65, 9, 158, 161, 160}

    Returns: 775

  46. {23, 19, 15, 68, 43, 2, 55, 73, 58, 51, 28, 63, 39, 1, 31, 48, 9, 67, 42, 17, 54, 24, 8, 38}

    Returns: 256

  47. {66, 21, 64, 56, 53, 63, 52, 37, 31, 60, 30, 70, 13, 5, 42, 12, 2, 55, 58, 11, 57, 23, 16, 50, 29, 71, 69, 4, 15, 65, 44, 14, 38, 43, 41, 39, 8, 25, 20, 1, 45, 40, 49, 51, 10, 7, 3}

    Returns: 271

  48. {3, 10, 6, 1, 9}

    Returns: 19

  49. {24, 58, 57, 11, 54, 46, 17, 53, 31, 9, 39, 65, 41, 45, 33, 22, 3, 1, 8, 51, 40, 35, 29, 56, 21, 2, 27, 4, 52, 15, 20, 63, 55, 50, 67, 23, 42, 30, 64, 10}

    Returns: 255

  50. {362420, 298174, 53151, 517301, 214948, 398582, 93351, 216341, 157757, 456735, 538796, 372220, 94932, 25567, 450340, 273221, 482687, 242892, 471444, 388810, 386304, 227276, 77738, 138386, 268815, 286653, 87398, 519576, 306619, 135187, 280400, 376796, 270299, 57031, 488962, 11562, 557215, 483511, 473515, 169111, 927, 69367, 368897, 134306, 471438, 101293, 353499}

    Returns: 2845156

  51. {21, 45, 7, 12, 32, 34, 44, 53, 40, 2, 59, 70, 58, 39, 51, 31, 38, 79, 75, 80, 22, 64, 55, 29, 66, 67, 60, 56, 65, 16, 23, 6, 57, 19, 18, 3, 69, 4, 68, 10}

    Returns: 319

  52. {69, 45, 79, 126, 71, 144, 201, 160, 121, 253, 4, 150, 117, 255, 81, 188, 106, 77, 170, 13, 230, 32, 21, 22, 80, 58, 146, 167, 90, 92, 189}

    Returns: 717

  53. {7, 6, 29}

    Returns: 36

  54. {516, 415, 756, 497, 815, 727, 610, 53, 266, 503, 849, 52, 411, 188, 836, 374, 398, 854, 234, 429, 8, 558, 313, 309, 434, 342, 92, 356, 677, 540, 90, 404, 445, 741, 430, 729, 172, 1, 315, 693, 761}

    Returns: 3115

  55. {11, 42, 52, 1, 32, 36, 49, 30, 47, 39, 44, 31, 25, 40, 43, 23, 9, 22, 17, 27, 35, 13, 38, 4, 28, 16}

    Returns: 160

  56. {687573, 148231, 123594, 215905, 103863, 745263, 308400, 448011, 374735, 145629, 94908, 616119, 238756, 691605, 371350, 444098, 119748, 753306, 227759, 450295, 17114, 685987, 315900, 423554, 632703, 678920, 594632, 702758, 703409, 747671, 53304, 628785, 498254, 463125}

    Returns: 3915310

  57. {78, 42, 35, 16, 9, 49, 29, 13, 89, 15, 26, 6, 74, 85, 77, 30, 48, 38, 11, 3, 37, 21, 28, 52, 22, 88, 40, 51, 65, 79, 27, 43, 47, 19, 68, 44, 50, 69, 66, 17, 25, 2, 34, 18, 67}

    Returns: 335

  58. {27279, 38726, 79623, 72632, 54465, 54505, 28029, 2217, 44249, 13454, 42645, 73459, 40686, 66519, 70561, 14285, 51141, 67984, 26865, 84374, 61696, 41481, 55409, 18040, 66735, 65580, 41748, 49076, 93253, 19971, 8252, 55194, 19824, 27512, 55258, 90254, 74514, 16712, 39757, 71714, 80608, 73001, 6552, 70448, 11793, 23557, 45467, 87889, 350}

    Returns: 480914

  59. {43915, 23933, 50818, 54069, 41356, 51458, 43017, 51161, 18734, 62420, 62996, 12228, 8836, 48794, 31326, 23777, 56108, 13297, 16801, 31222, 54990, 49279, 13780, 28259}

    Returns: 287051

  60. {18, 50, 55, 27, 38, 62, 54, 21, 48, 33, 19, 46, 58, 81, 3, 15, 79, 16, 11, 4, 68, 72, 10, 63, 41, 83, 35, 37, 23, 31, 2, 47, 85, 44, 26, 82, 20, 57, 86, 52, 65, 64, 1}

    Returns: 351

  61. {4, 14, 10, 12, 9, 7, 13, 6}

    Returns: 31

  62. {517, 554, 490, 32, 68, 329, 548, 174, 498, 570, 459, 246, 311, 371, 399, 66, 346, 216, 560, 315, 435, 440, 98, 237, 518, 426, 108, 385, 136, 332, 313, 411, 422, 393, 161, 156, 558, 539, 436, 138, 369}

    Returns: 2384

  63. {296, 76, 57, 114, 45, 139, 2, 128}

    Returns: 671

  64. {17, 32, 7, 1, 11, 18, 3, 36, 37, 26, 20, 28, 6, 24, 4, 33, 35, 31, 38, 19}

    Returns: 111

  65. {11213, 37708, 14156, 31166, 18120, 4730, 10346, 19488, 35237, 13992, 41111}

    Returns: 132176

  66. {17, 23, 15, 6, 2, 9, 34, 20, 21, 24, 28, 14, 32, 10, 19, 11, 13}

    Returns: 97

  67. {610204, 584712, 449378, 12765, 703332, 239001, 264633, 790742, 544307, 732895, 351415, 506164, 586536, 571527, 377204, 508503, 621983, 776069, 340717, 597494}

    Returns: 3346036

  68. {476, 694, 293, 123, 243, 726, 532, 150, 709, 371, 841, 472, 461, 234, 558, 616, 716, 730, 1, 576, 816, 803, 826}

    Returns: 3169

  69. {34334, 12030, 649, 3236, 25750, 7138, 38098, 4458, 35455, 2790, 10195, 46572, 39176, 4180, 15737, 30267, 6163, 49450, 36286, 12200, 39745, 24830, 8066, 7616, 24779, 40067, 16242, 6706, 44625, 1427, 37743, 24464, 37575, 14552, 16071, 42727, 5985, 41623, 31555, 25206, 19116, 29675, 5476, 15536}

    Returns: 211930

  70. {12, 43, 75, 70, 21, 36, 58, 4, 37, 1, 56, 11, 41, 52, 72, 77, 62, 80, 17, 2, 49, 78, 8, 9, 22, 34, 67, 14, 28, 24, 69, 7, 39, 71, 73, 74, 45, 27, 30, 60}

    Returns: 327

  71. {6, 11, 12, 3, 21, 13, 10, 14, 20, 8, 23, 1, 18, 17, 22}

    Returns: 63

  72. {68, 8, 19, 76, 11, 37, 36, 40, 3, 20, 1, 17, 7, 42}

    Returns: 175

  73. {486248, 483078, 243431, 353500, 243689, 602451, 510500, 349884, 338388, 226369, 295881, 297631, 503184, 140417, 255238, 541206, 549058, 628772, 214774, 296937, 428729, 11891, 223489, 167700, 384445, 117294, 294042, 145421, 483503, 141265, 309963, 650386, 549846, 12668, 281379, 640277, 300311, 380234, 333245}

    Returns: 3156539

  74. {1964, 1785, 321, 669, 726, 1004, 382, 1021, 992, 912, 1407, 1667, 1516, 2215, 1454, 1629, 699, 1967, 872, 1607, 1787, 1192, 1818, 1633, 2111, 1135, 1367, 1790, 1987, 1758, 1904, 582, 1764, 2127, 200, 633, 246}

    Returns: 7723

  75. {7151, 18657, 11676, 1114, 10377, 8415, 6419, 14688, 1131, 14499, 5239, 2844, 26435, 5543, 9207, 10427, 7710, 19535, 12190, 14571, 11359, 27524, 16069, 14088, 1815, 2106, 13197, 3917, 5826, 24400, 12626, 22037, 4039}

    Returns: 111104

  76. {593266, 651571, 622661, 560109, 31359, 55079, 22197, 595865, 648141, 156932, 624186, 306705, 407922, 325358, 87763, 283954, 103979, 152964, 520260, 294439, 583218, 129084, 202128, 242978, 330775, 227247, 518995, 309397, 300254, 102563, 60291, 27253}

    Returns: 2977766

  77. {14, 31, 44, 23, 54, 33, 47, 42, 7, 20, 38, 22, 13, 10, 39, 2, 45, 35, 26, 12, 28, 52, 9, 41, 1, 24, 17}

    Returns: 167

  78. {481, 1475, 1440, 1249, 1619, 593, 523, 1587, 1480, 1438, 242, 371}

    Returns: 4988

  79. {15, 18, 7, 16, 5, 8}

    Returns: 33

  80. {3895, 2310, 976, 8384, 8866, 9635, 874, 2686, 4107, 4449, 2545, 7357, 11470, 3569, 1807, 2911, 4008, 6921, 5610, 3523, 9762, 3344, 561, 1464, 345, 10745, 12030, 5054, 7008, 6948}

    Returns: 40066

  81. {5895, 4665, 4906, 3751, 4213, 1509, 1452, 5652, 2354, 3769, 379, 3370, 1508, 5192, 5303, 111, 3583, 5840, 1533, 2686, 4902, 5837, 2100, 5642, 2138, 5085, 3677, 1044, 4504, 2242, 3371, 3340, 3428, 5724, 600, 6350, 2557, 3001, 6093, 6440, 481}

    Returns: 32095

  82. {503, 599, 232, 170, 362, 191, 663, 335, 558, 156, 674, 211}

    Returns: 1831

  83. {20, 43, 37, 35, 26, 31, 6, 10, 11, 8, 16, 33, 9, 45, 48, 47, 49, 27, 12, 39, 36, 4, 23, 41, 42, 22, 24, 17, 28, 3, 2, 1, 40, 38, 7, 19, 34, 21, 44, 25, 15, 30, 13, 5, 14, 46}

    Returns: 191

  84. {39626, 23544, 4889, 14778, 349, 6341}

    Returns: 84289

  85. {4058, 7146, 12492, 16799, 23522, 17322, 32996, 4916, 24574, 16365, 27522, 5207, 900, 21328, 9963, 15336, 26920, 33943, 12416, 21471, 2044, 12766, 8586, 10186, 32057, 14393, 24550, 3172, 5761}

    Returns: 133797

  86. {14128, 62674, 31770, 43393, 70185, 77397, 48353, 10864, 54916, 69439, 40593, 26345, 18539, 33568, 13521, 36588, 75681, 11679, 55553, 63462, 36168, 69472, 33225, 34952, 75597, 6474, 37778, 4189, 8068, 57636}

    Returns: 350338

  87. {561875, 561874}

    Returns: 561875

  88. {28895, 28885, 28900, 28886, 28881, 28870, 28864, 28866, 28863, 28898, 28875, 28894, 28906, 28880, 28904, 28907, 28869, 28878, 28889, 28867, 28884, 28874, 28905, 28873, 28868, 28892, 28861, 28882, 28862, 28879, 28901, 28888, 28876, 28899, 28893, 28859, 28890, 28891, 28903, 28902, 28865, 28887, 28877, 28896, 28872, 28897, 28871, 28860, 28883, 28858}

    Returns: 173247

  89. {7729, 7733, 7728, 7731, 7736, 7734, 7732, 7735, 7730}

    Returns: 30927

  90. {43606, 43627, 43626, 43607, 43608, 43631, 43620, 43611, 43613, 43615, 43629, 43617, 43616, 43610, 43612, 43623, 43622, 43621, 43630, 43619, 43605, 43625, 43632, 43624, 43628, 43618, 43614, 43609, 43604, 43603}

    Returns: 218111

  91. {254, 251, 260, 247, 244, 267, 259, 248, 252, 253, 249, 265, 246, 250, 257, 256, 261, 266, 255, 245, 262, 264, 258, 263}

    Returns: 1039

  92. {6844, 6843, 6836, 6820, 6817, 6815, 6825, 6816, 6826, 6842, 6804, 6821, 6839, 6835, 6846, 6822, 6818, 6828, 6845, 6807, 6837, 6841, 6824, 6812, 6805, 6809, 6831, 6832, 6827, 6806, 6830, 6834, 6814, 6811, 6823, 6813, 6838, 6810, 6829, 6833, 6819, 6840, 6808, 6803}

    Returns: 34111

  93. {9431, 9446, 9438, 9445, 9443, 9436, 9429, 9442, 9435, 9428, 9426, 9447, 9432, 9444, 9437, 9425, 9434, 9448, 9439, 9441, 9430, 9433, 9427, 9440}

    Returns: 47151

  94. {531, 537, 544, 539, 534, 547, 533, 546, 536, 538, 535, 541, 542, 543, 540, 548, 545, 530, 532}

    Returns: 2175

  95. {579, 575, 572, 580, 577, 576, 574, 578, 581, 573}

    Returns: 1735

  96. {229267, 229271, 229251, 229264, 229255, 229261, 229252, 229277, 229256, 229268, 229262, 229265, 229273, 229276, 229258, 229253, 229269, 229270, 229275, 229257, 229263, 229259, 229266, 229260, 229274, 229254, 229272}

    Returns: 917071

  97. {479, 494, 477, 481, 487, 488, 478, 492, 491, 486, 483, 480, 485, 482, 490, 484, 489, 493, 476}

    Returns: 1935

  98. {93628, 93637, 93624, 93640, 93635, 93634, 93629, 93627, 93639, 93638, 93649, 93646, 93641, 93647, 93643, 93631, 93645, 93633, 93632, 93630, 93644, 93625, 93636, 93642, 93626, 93648}

    Returns: 468191

  99. {787876, 787922, 787899, 787883, 787902, 787915, 787921, 787907, 787881, 787898, 787880, 787891, 787901, 787879, 787894, 787889, 787908, 787917, 787892, 787909, 787918, 787916, 787895, 787893, 787923, 787911, 787912, 787920, 787914, 787904, 787906, 787885, 787887, 787900, 787882, 787903, 787888, 787878, 787877, 787919, 787910, 787890, 787886, 787905, 787896, 787884, 787897, 787913}

    Returns: 3939551

  100. {15, 23, 40, 44, 39, 35, 36, 31, 22, 42, 18, 34, 30, 41, 19, 24, 37, 20, 27, 38, 29, 16, 21, 43, 33, 17, 26, 32, 25, 28}

    Returns: 159

  101. {2509, 2482, 2504, 2505, 2479, 2502, 2506, 2491, 2496, 2477, 2484, 2501, 2511, 2494, 2481, 2485, 2488, 2497, 2510, 2489, 2490, 2495, 2493, 2508, 2487, 2499, 2492, 2480, 2498, 2507, 2486, 2500, 2478, 2483, 2503}

    Returns: 12479

  102. {41, 43, 34, 29, 35, 48, 45, 30, 38, 27, 44, 33, 46, 36, 31, 39, 28, 25, 32, 47, 37, 40, 42, 49, 26}

    Returns: 191

  103. {9818, 9787, 9789, 9800, 9814, 9799, 9803, 9806, 9805, 9797, 9812, 9801, 9791, 9809, 9792, 9802, 9808, 9786, 9785, 9788, 9795, 9798, 9811, 9794, 9815, 9790, 9816, 9793, 9804, 9817, 9796, 9813, 9810, 9807}

    Returns: 48991

  104. {65, 77, 72, 87, 76, 58, 89, 86, 82, 64, 59, 81, 73, 75, 70, 80, 61, 71, 74, 56, 63, 66, 83, 79, 88, 62, 84, 60, 85, 67, 78, 90, 68, 57, 69}

    Returns: 351

  105. {66847, 66866, 66844, 66859, 66849, 66857, 66862, 66860, 66858, 66861, 66845, 66853, 66856, 66842, 66846, 66850, 66840, 66854, 66851, 66865, 66868, 66867, 66863, 66839, 66848, 66852, 66841, 66843, 66855, 66864}

    Returns: 334271

  106. {4008, 3984, 3982, 3980, 3996, 3976, 3990, 3965, 3969, 3995, 3999, 3975, 4006, 3971, 3978, 3967, 3991, 3972, 3964, 3963, 3998, 4002, 3970, 3973, 3981, 4005, 3983, 3988, 3985, 4003, 3994, 4004, 4000, 4007, 3989, 3993, 4001, 3974, 4009, 3968, 3977, 3986, 3966, 3992, 3987, 3997, 3979}

    Returns: 23871

  107. {77, 68, 78, 71, 70, 63, 75, 76, 67, 65, 81, 69, 61, 66, 62, 79, 73, 72, 74, 80, 64}

    Returns: 351

  108. {6736, 6756, 6762, 6758, 6740, 6760, 6746, 6729, 6745, 6748, 6733, 6751, 6750, 6726, 6734, 6771, 6743, 6770, 6725, 6755, 6769, 6754, 6766, 6732, 6763, 6728, 6737, 6757, 6767, 6768, 6759, 6738, 6747, 6765, 6727, 6731, 6739, 6742, 6741, 6764, 6752, 6749, 6761, 6730, 6744, 6735, 6753}

    Returns: 33791

  109. {466132, 466131}

    Returns: 932263

  110. {17}

    Returns: 17

  111. {27112, 27107, 27098, 27125, 27124, 27131, 27115, 27126, 27108, 27106, 27103, 27109, 27127, 27097, 27116, 27118, 27095, 27105, 27132, 27102, 27130, 27093, 27110, 27099, 27113, 27119, 27096, 27111, 27121, 27114, 27122, 27120, 27117, 27100, 27101, 27123, 27128, 27104, 27094, 27129}

    Returns: 135551

  112. {104825, 104810, 104793, 104819, 104820, 104816, 104815, 104800, 104822, 104807, 104808, 104813, 104809, 104817, 104829, 104796, 104830, 104806, 104821, 104802, 104798, 104811, 104799, 104794, 104801, 104826, 104818, 104824, 104827, 104823, 104804, 104812, 104814, 104795, 104805, 104803, 104828, 104797, 104792}

    Returns: 524031

  113. {8881, 8882, 8885, 8883, 8884}

    Returns: 26647

  114. {2382, 2383}

    Returns: 2383

  115. {77035, 77042, 77036, 77047, 77039, 77038, 77048, 77032, 77045, 77037, 77044, 77043, 77031, 77040, 77034, 77030, 77041, 77033, 77046}

    Returns: 308175

  116. {680595, 680581, 680598, 680608, 680602, 680605, 680576, 680592, 680564, 680565, 680572, 680562, 680603, 680573, 680587, 680591, 680579, 680580, 680606, 680574, 680568, 680567, 680594, 680586, 680588, 680597, 680590, 680569, 680601, 680575, 680604, 680584, 680582, 680563, 680577, 680566, 680589, 680583, 680600, 680596, 680599, 680578, 680585, 680610, 680571, 680570, 680609, 680593, 680607}

    Returns: 4083519

  117. {15,31,7,23,27,47,11,29,30,63,39,55,13,59,14,43,61,62,79,19,45,46,95,51,71,87,21,53,54,91,111,22,57,75,93,94,127,58,103,143,119,25,35,60,77,123,78,107,125,126}

    Returns: 349

  118. {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288}

    Returns: 1048575

  119. {15,7,31,23,27,11,47,29,30,39,63,13,55,14,59,43,61,19,62,79,45,46,51,71,95,21,87,53,22,54,91,57,75,111,93,25,35,58,94,103,143,127,60,77,119,3,26,78,123,107}

    Returns: 349

  120. {983040,917504,950272,884736,851968,999424,753664,491520,933888,720896,966656,458752,901120,868352,770048,507904,819200,991232,737280,475136,835584,925696,688128,958464,704512,425984,442368,892928,638976,860160,761856,376832,499712,622592,802816,942080,987136,245760,729088,974848,360448,466944,786432,909312,876544,778240,516096,827392,921600,745472}

    Returns: 4714496

  121. {1,3,2,5,6,9,4,10,17,12,18,33,8,20,34,65,24,36,66,129,16,40,68,130,257,48,72,132,258,513,32,80,136,260,514,1025,7,96,144,264,516,1026,2049,11,13,19,64,160,272,520}

    Returns: 5250

  122. {524288,786432,262144,655360,393216,589824,131072,327680,557056,196608,294912,540672,65536,163840,278528,532480,98304,147456,270336,528384,32768,81920,139264,266240,526336,49152,73728,135168,264192,525312,16384,40960,69632,133120,263168,524800,24576,36864,67584,132096,262656,524544,917504,851968,8192,20480,34816,66560,131584,262400}

    Returns: 6291200

  123. {127586,888288,265580,798962,879744,643210,450726,102090,1,912856,79060,232018,113202,108360,506664,903142,570732,636146,548920,185326,539636,739392,591156,922008,123512,188168,558398,992330,66796,553100,153106,64106,95172,741388,92320,546382,999712,531848,410938,261690,688964,859790,154536,589652,327164,487490,31640,347688,242278,457906}

    Returns: 5178393

  124. {232152,589897,484556,919756,380641,780897,252924,378740,167432,910905,971176,909797,231453,736108,965188,596069,693941,2,730069,333928,762460,698560,712708,586400,631581,617620,717332,465796,573417,94232,519944,310344,892136,688456,458196,917408,129753,309804,100472,584912,756840,108648,687361,51033,46669,857025,603741,456968,832280,270216}

    Returns: 5395307

  125. {474419,39273,897875,769162,145921,878939,786211,587792,505001,445218,154145,26946,805042,585929,106641,696811,254833,767538,687865,286289,793371,640987,710616,273523,95402,846762,510946,820131,746753,834473,742162,770042,238496,865040,365338,265664,305810,623888,474627,892937,854105,220354,100530,549569,139907,838009,361616,4,210187,634786}

    Returns: 4564789

  126. {638242,8,391318,79792,389956,58272,879458,602547,302839,764834,387302,941927,491510,777329,949574,945268,79654,96912,298787,312293,875030,58370,339191,485346,631813,109555,382693,73239,34775,876385,823703,220402,84789,120513,593798,921122,836321,983799,334400,745171,924451,381221,980145,514966,733459,629156,215552,779092,828580,809233}

    Returns: 4707077

  127. {550691,26824,459014,972236,595594,358317,206537,245952,96038,16,575106,931015,305583,365603,677414,325477,857965,897030,20937,779425,497004,656302,948416,158857,374286,96101,857028,428002,200143,983757,664515,212271,828196,608421,890432,810445,630381,630119,261707,61130,282313,853793,702795,839296,391849,948078,89991,525889,271725,559680}

    Returns: 4921825

  128. {351552,979802,219228,236617,531546,817997,748289,685710,82767,766729,217734,45779,32,709004,457040,567053,62984,33232,367454,913371,196831,520397,498881,463062,824206,75035,793626,110855,37701,688085,126162,924819,836690,844122,793744,355985,843152,472589,479451,118045,680972,724253,701388,633157,503508,548702,896846,130112,149151,172822}

    Returns: 4069738

  129. {614558,151603,887860,584472,515001,624695,768794,264205,565387,895381,64,212768,299547,151051,35231,597423,283951,383503,575108,481701,566789,66461,187039,960913,449180,123550,552352,72226,400173,728246,629652,902402,952247,989354,46979,363787,311480,904749,752441,977322,570295,413702,593698,529167,291262,999199,69262,619790,347174,980780}

    Returns: 4409211

  130. {989269,982026,345461,716820,325642,39261,926722,642645,832769,773720,744291,733261,328983,857868,780633,369278,638254,98901,644644,199037,251205,46191,40298,464974,78386,891682,194369,462699,995135,242713,714265,128,261983,929617,319817,6944,516683,882797,633972,69953,590398,390182,455448,967014,729097,293919,116275,786698,191763,991766}

    Returns: 4916494

  131. {81097,983281,559862,878199,339523,266782,345738,927910,155225,213719,177677,407564,49813,264214,811101,888973,92774,88168,552461,842920,282248,256,361689,511561,426626,816812,830133,824492,626889,634896,193150,473704,25154,118788,590418,585440,463973,788710,82043,766145,768125,936042,901190,129784,283723,234702,838322,643252,184522,651317}

    Returns: 5219154

  132. {190483,637390,355491,323768,236972,566406,978132,17873,980408,15776,201081,322705,716957,40203,131152,26693,912792,101784,901534,285944,723975,753722,66572,886152,607313,215276,534940,798741,512,314802,627846,275541,924839,694455,878771,560388,290098,838869,539029,881017,834891,138484,952609,340116,319779,200969,518314,91412,620950,450880}

    Returns: 4424442

  133. {434757,877228,702901,43473,922582,162123,508763,774675,573512,514173,936959,336175,573571,344282,506279,4594,907267,946578,716884,872579,527023,450905,415911,971676,1024,840239,233696,268774,39298,514123,105089,248433,127270,623139,877393,224013,887605,422555,946748,279239,766417,31431,552984,446659,449043,121503,917890,213043,228152,560126}

    Returns: 4629589

  134. {817073,456248,287639,766879,344639,29047,119925,602227,479832,807765,852524,779967,712946,95008,554529,685682,713619,389161,2048,714675,835853,315508,337157,431198,443928,418377,499946,443628,394954,689319,881771,271665,911029,87000,931703,664062,202141,406176,939432,827494,331860,856975,930670,99614,328116,194358,915418,368958,684089,87670}

    Returns: 4508083

  135. {729764,715577,633203,576171,836536,851968,412648,969647,560841,655820,633173,484493,35734,76834,716051,804911,296169,642123,861895,329533,945758,181678,8565,11139,978882,467467,600364,106562,788567,954129,380319,246928,577331,101085,696532,838060,274055,427473,484277,99426,510269,4096,749508,470743,257979,919627,910188,658290,511813,633756}

    Returns: 5086844

  136. {940135,741375,727866,951051,350561,775247,494282,332678,377996,754145,889713,826474,789756,380676,200208,592218,872317,956658,233181,86389,498872,312621,333919,761275,887550,313220,597701,333416,219764,873653,136804,428645,311515,458988,8192,284052,728379,950378,625541,626569,82732,541057,335019,312153,33793,527227,183395,708234,509137,955803}

    Returns: 4436655

  137. {267241,466275,498107,796888,984763,426613,466132,861285,374347,964713,73436,34680,102626,36045,885578,233783,731605,438278,435701,626257,41976,997336,950618,375892,593201,331859,81148,11564,298215,822302,895974,296697,298136,205657,43852,893899,394378,662194,16384,527933,832153,930438,302560,70827,697007,822577,396284,689105,802322,799476}

    Returns: 5096669

  138. {419585,32280,746498,77201,419264,87861,77415,204587,940478,545397,200341,603128,7601,399429,725453,859780,67917,67307,268262,725595,228450,795990,944893,671651,25233,74383,926394,17447,677804,787663,728826,32768,475306,489003,16734,462218,537411,344427,535408,343469,423726,679224,542125,484916,934261,278451,228595,24072,347057,603682}

    Returns: 4149093

  139. {925146,944296,263237,302276,839947,147647,710855,159773,11118,546269,446672,158669,821093,189471,161847,446114,176295,137585,397205,683745,55140,397135,189749,919896,144063,814041,273703,317439,943482,680780,396275,312586,799216,65536,525547,918990,923131,708425,157402,164237,148534,977017,4248,927328,839580,149428,409407,706496,714703,281886}

    Returns: 5099995

  140. {639472,563509,814454,37807,875083,75581,293680,363941,370022,612159,121777,2595,313697,860546,65830,608396,124879,106839,646530,131072,603327,382306,281362,532973,64807,618552,803774,620744,323628,79076,267166,596056,877329,29892,895734,93610,587449,347665,619344,865840,338202,69692,628853,288309,808192,1523,613831,368556,545147,633218}

    Returns: 4524831

  141. {570465,141607,609303,91005,164305,99734,731998,730704,728981,8924,73739,240388,78776,239606,625334,546083,129322,70231,529695,622219,218062,717137,203155,650026,99950,94877,661928,57625,595662,85447,262144,580945,765470,573752,12792,206478,199432,729761,680752,90047,707882,532162,658279,180134,547230,221140,211117,248210,210676,647961}

    Returns: 4037675

  142. {131191,338561,469182,183786,120935,282576,446057,456132,132847,180727,375589,307162,411920,79941,386535,428458,352729,101016,134397,311444,394462,365259,42130,455324,21590,304140,60512,100942,102358,316363,396786,190780,189990,100174,365205,385443,178685,323425,123483,170924,123359,127083,227851,186318,370511,289053,457128,520144,147633,524288}

    Returns: 2910552

  143. {289383, 930886, 692777, 636915, 747793, 238335, 885386, 760492, 516649, 641421, 202362, 490027, 368690, 520059, 897763, 513926, 180540, 383426, 89172, 455736, 5211, 595368, 702567, 956429, 465782, 21530, 722862, 665123, 174067, 703135, 513929, 979802, 634022, 723058, 133069, 898167, 961393, 18456, 175011, 478042, 176229, 377373, 484421, 544919, 413784, 898537, 575198, 594324, 798315, 664370 }

    Returns: 4503867

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: