Statistics

Problem Statement for "XorSequenceEasy"

Problem Statement

You are given a int[] A and an int N that is a power of 2. All elements of A are between 0 and N-1, inclusive.

You can now choose an integer B which is between 0 and N-1, inclusive. This integer determines a new sequence C defined as follows: For each valid i, C[i] = (A[i] xor B).

Given the sequence C, we will count the pairs of indices (i,j) such that both i<j and C[i]<C[j]. Compute and return the largest result we can obtain.

Definition

Class:
XorSequenceEasy
Method:
getmax
Parameters:
int[], int
Returns:
int
Method signature:
int getmax(int[] A, int N)
(be sure your method is public)

Notes

  • XOR (exclusive or) is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.
  • For example 42 XOR 7 is performed as follows. First, the numbers are converted to binary: 42 is 101010 and 7 is 111. Then the shorter number is prepended with leading zeros until both numbers have the same number of digits. This means 7 becomes 000111. Then 101010 XOR 000111 = 101101 (the result has ones only in the positions where the two numbers differ). Then the result can be converted back to decimal notation. In this case 101101 = 45, so 42 XOR 7 = 45.

Constraints

  • N will be between 2 and 1,073,741,824 (2^30), inclusive.
  • N will be a power of 2.
  • The number of elements in A will be between 1 and 50, inclusive.
  • Each element in A will be between 0 and N-1, inclusive.

Examples

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

    4

    Returns: 8

    For B=3 we get C={0,1,2,3,0,1}. For this C there are 8 pairs (i,j) such that i<j and C[i]<C[j]. These are the 8 pairs: (0,1), (0,2), (0,3), (0,5), (1,2), (1,3), (2,3), and (4,5). No other choice of B produces more than 8 pairs.

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

    8

    Returns: 21

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

    16

    Returns: 76

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

    8

    Returns: 0

    Regardless of the value of B you choose, all elements in C will be equal. Thus, the number of pairs we seek is always zero.

  5. {408024109,11635919,196474438,117649705,812669700,553475508,445349752,271145432,730417256,738416295 ,147699711,880268351,816031019,686078705,1032012284,182546393,875376506,220137366,906190345,16216108 ,799485093,715669847,413196148,122291044,777206980,68706223,769896725,212567592,809746340,964776169 ,928126551,228208603,918774366,352800800,849040635,941604920,326686120,920977486,964528038,659998484 ,207195539,607901477,725914710,655525412,949610052,142750431,766838105,1024818573,836758851,97228667}

    1073741824

    Returns: 720

  6. {0}

    2

    Returns: 0

  7. {0,1}

    2

    Returns: 1

  8. {0,0}

    2

    Returns: 0

  9. {1,0}

    2

    Returns: 1

  10. {1,1}

    2

    Returns: 0

  11. {1,1,0,1,1,0,0,0,1,1,1}

    2

    Returns: 14

  12. {1,0,1,1,0,1,0,0,0,0,1,1,1,1,0,1,1,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1,0,0,1,0}

    2

    Returns: 181

  13. {0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,1,0,0,1,0,0,0,1,1,0,0,1}

    2

    Returns: 128

  14. {1,0,0,0,0,1,0,0,1,1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,1,0,1,0,0,1,1,1,1,1,0,0}

    2

    Returns: 186

  15. {2,1,3,3,1,3,0,1,0,1,3,1,0,3,3,1,3,1,2,2,1,1,0,0,0,1,0,2,2,1,2,0,3,1,2,3,3,3,0,0,3,1,3}

    4

    Returns: 376

  16. {1,2,2,1,3,3,2,0,2,1,0,1,1,3,1,0,2,3,1,1,2,0,0,3,1,2,2}

    4

    Returns: 142

  17. {2,3,3,0,2,2,1,1,3,3,0,3,2,3,1,3,1,2,3,2,3,0,3,3,3,0}

    4

    Returns: 128

  18. {1,2,1,0,3,1,2,3,1}

    4

    Returns: 17

  19. {6,4,3,3,1,2,1,3,0,0,2,0,1,5,5,1,6,4,1,0,0,0,5,1,0,4,0,2,1,6,1,3,1,7,6}

    8

    Returns: 290

  20. {0,2,6,7,1,6,0,1,3,4,4,2,4,3}

    8

    Returns: 46

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

    8

    Returns: 34

  22. {4,5,7,3,5,2,0,6,1,1,1,0,3,3,0,4,5,6,3,7,4,2,2,1,0,0,5,4,3,5,3,4,5,1,7,3,2,4,1,7,4,2,6,4}

    8

    Returns: 474

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

    16

    Returns: 617

  24. {8,12,12,4,2,14,10,11,11,15,4,10,8,12,8,2,5,5,11,4,8,8}

    16

    Returns: 132

  25. {15,1,12,15,5,13,13,0,14,11,13,3,4,15,3,9,3,7,15,2,13}

    16

    Returns: 117

  26. {1,12,0,14,3,6,1,13}

    16

    Returns: 16

  27. {4,26,16,5,15,19}

    32

    Returns: 9

  28. {15,8,9,20,11,20,15,24,10,21,23,2,8,19,22,23,26,14,28,8,2,13,8,23,13,9,14,4,25,23,3,16,0,0,10,14,29,29}

    32

    Returns: 362

  29. {20,11,14}

    32

    Returns: 3

  30. {2,6,5,13}

    32

    Returns: 6

  31. {33,50,1,33,37,36,1,10,18,32,30,55,59,51,46,45,5}

    64

    Returns: 82

  32. {49,44,29,53,54,13,28,42,4,24,45,47,29,50,39,60,17,0,6,28}

    64

    Returns: 120

  33. {62}

    64

    Returns: 0

  34. {3,6,50,37,2,54,13,41,22,45,5,28,3,6}

    64

    Returns: 55

  35. {37,9,116,113,103,81,41,39,118,103,6,76,23,48,27,29,111,58,114,23,46,126,23,47,75,58,83,114,91,98}

    128

    Returns: 251

  36. {120,8,97,103,22,48,30,120,14,47,125,28,111,15,38,6,13,106,75,53,3,16,112,84,62,27,104,83,46,44,44,31,49,5,42,63,102,121}

    128

    Returns: 401

  37. {1,117,72,40,68,18,41,23,2,52,60,4,124,39,44,25,114,115,104,69,77,15,30,72,12,51,33,78,19,21,110,39,75,39,22,63,30,92,79,37,119,82}

    128

    Returns: 485

  38. {79,6,11,114,36,76,50,96,108,11,74,32,91,71,77,109,54,104,46,30,116,124,72,19,19,104,46,125,33,124,97,118,120,27,74,73,17,42,104,26,58,113}

    128

    Returns: 494

  39. {38,241,152,153,138,218,37,203,94,231,179,117,35,62,188,164,234,191,108,113,3}

    256

    Returns: 134

  40. {128,79,111,38,24,39,90,26,57,98,208,175,180,215,48,204,10,215,178,18,220,94,92,242,192}

    256

    Returns: 194

  41. {170,194,254,136,185,248,110,147,231,88,54,199,214,86,37,100,17,1,217,73,51}

    256

    Returns: 153

  42. {39,202,177,206,134,233,200,69,224,250,87,167,89,125,93,105,136,222,87,64,152,130,255,102,55,5,213,68,223,21,140,191,208,106,109,172}

    256

    Returns: 365

  43. {460,303,130,1,413,182,218,301,220,61,397,80,385,115,2,147,147,453,57,230,425,291,505,208,288,219,365,403,260,85,352,208,46,91,497,57,101,222,475,198,188,430,131,414,279,482,449,151,82,222}

    512

    Returns: 656

  44. {84,389,74,112,383,111,241,222,48,175,33,53,199,194,94,46}

    512

    Returns: 85

  45. {239,477,116,34,163,27,423,22,65,163,136,262,471,138,30,132,27,257,374,285,129,81,255,396,136,177,116}

    512

    Returns: 193

  46. {488,473,110,379,4,94,483,9,356,261,414,160,359,372,60,8,145,349,434,145,188,144,5,463,431,444}

    512

    Returns: 197

  47. {683,1005,1018,983,144,202,834,467,776,409,590}

    1024

    Returns: 40

  48. {34,1015,523,97,471,112,568,390,608,233,255,421,483,768,756,753,835,397,178,965,420,961,487,757,159,886,552,694,797,203,132,661,266}

    1024

    Returns: 304

  49. {752,80,904,647,92,454,581,479,759,604,102,74,520,146,72,577,762,171,147,934,577,687,696,517,378,250}

    1024

    Returns: 181

  50. {224,871,57,872,386,674,571,289,212,63,509,312,937,625,137,958,577,935,892,867,232,809,736,408,571,917,162}

    1024

    Returns: 206

  51. {688,1233,1877,30,1347,147,1234,1539,264,1342,1653,813,1087,405,187,1237,332,1791,1531,1408,1619,726,33,1638,753,1062,1802,1987,1628,280,143}

    2048

    Returns: 256

  52. {1267,174,928,894,130,381,1430,731,1085,790,1757,1988,550,207}

    2048

    Returns: 56

  53. {1711,1344,103,1897,1636,46,2023,391,770,1146,945,1800,1299,350}

    2048

    Returns: 58

  54. {206,384,936,1990}

    2048

    Returns: 6

  55. {2751,76,286,70,1340,747,185,2545,1540}

    4096

    Returns: 25

  56. {898,2166,803,1804,351,835,1663,1347,1953,1270}

    4096

    Returns: 38

  57. {1967,4073,3192,3941,78}

    4096

    Returns: 6

  58. {442,687,2600,2889,3055,3749,112,1173,601,3798,1848,505,2264,2185,2762,970,453,2862,994,2397,1920,3191,2877,2405}

    4096

    Returns: 165

  59. {8131,5929,978,6732,5229,47,3758,1056,5941}

    8192

    Returns: 25

  60. {545,19,7493,4314,1742,6955,5072,7047,1006}

    8192

    Returns: 23

  61. {2781,7516,6835,6938,3397,575,2391,7785,6074,1417,7252,4436,5630,843,7900,6487,5293,2360,3779,4778}

    8192

    Returns: 112

  62. {6678,2880,7169,6580,4754,2856,5417,4579,2898,3582,6498,3575,4242,3485,7369,3368,3210,7049,3691,2481,1481,8053,811,4140,1696,7014,8150}

    8192

    Returns: 217

  63. {5394,6010,7761,3676,7352,6880,8918,14014,13240,8989,15875,12906,15115,11749,10023,4006,15957,16034,844,3771,8880,5693,225,12794,7004,11484,6455,10547,12600,70,12292}

    16384

    Returns: 278

  64. {15381,482,12745,6202,1223,4814,15265,3231,2693,12002,7639,8062,5882,14006,1565}

    16384

    Returns: 63

  65. {2173,12285,8748,11224,15041,14739,10214,9629,4563,10189,12333,13921,4873,1361,15781,12795,14728,14077,9200,6034,14804,5546,3770,12728,14151,14614,7520,11270,10521,6886,8337,14376,4238,626,13812,7466,2193}

    16384

    Returns: 413

  66. {13087,10559,5752,1511,14361,10495,3402,734,659,15308,14045,11174,6457,9399,6559,13619,521,9795,15710,7521,2850,11987,1524,12625,4815}

    16384

    Returns: 169

  67. {30329,24239,1311,22017,11350,27485,909,32349,13506,13126,26885,8936,15058,27723,25167}

    32768

    Returns: 67

  68. {32241,22392,9247,29610,12855,2955,25688,8969,25405,27163,8093,28848,20614,1338,5681,3275,15957,22964,1,4901,30785,4388,28247,4990,31198,12713,22190,15905,28535,5512,15502,781,12871,1718,17549,19570,4891,24441,18337,27421,22886,31989,24691,28030}

    32768

    Returns: 542

  69. {12636,15144,7501,23842,13373,32697,15536,3363,30398,3740,22377,7971,21147,812,26474,20074,919,20165,764,20809,26411,1618,30321,5459,29622,10842,16522,2151,31388,17056,26694,15125,1510,21073,6483,3204,21794,9248,15074,11782}

    32768

    Returns: 408

  70. {9788,12126,7063,19605,28838,19417,30615,2071,17593,6220,31109,20502,32395,5819,6803,302,28612,15378,17883,24930,19360,21070,19970}

    32768

    Returns: 161

  71. {50302,38310,9601,16065,20661,48633,35533,10310,3501,4170,56424,43818,12793,39278,52225,10184,30733,28910,63722,34061,59411,16748,17237,7239,42810,18394,12389,46816,12703,17716}

    65536

    Returns: 258

  72. {25967,39366,19359,578,65377,2184,63749,16848,27410,29378,47870,9327,39461,31342,4776,51491,19470,7886,63551,41481,29667,40688,15868,39928,1319,57980,64810,29362,20639,31401,20481,29427,3163,44945,2970,9933,7324,59696,20412,6272}

    65536

    Returns: 449

  73. {42621,7010,37545,35765,11359,62748,31562,65407,26885,64248,10318,11664,31424,32409,49377,58109,56064,58651,60784,14269,56022,55099,41451,60567,40361,29292,45253,31168,50352,63318,60155,18007,63964,19119,20409,14738,26349,13069,34550,13663,3392}

    65536

    Returns: 470

  74. {33602,6677,2089,51832,63893,59969,58944,7251,51285,42901,53627,34821,43634}

    65536

    Returns: 54

  75. {51782,25053,101930,112955,23148,100959,53940,67093,10662,79011,123491,33056,103082,32766,18744,7213,50212,129321,88266,124771,8520,105263,51929,28161,14597,55734,125461,42848,1362,89642,112181,62754}

    131072

    Returns: 273

  76. {48150,129809,104698,12051,3978,99339,122482,22844}

    131072

    Returns: 18

  77. {43790,105113,60743,12363,102158,129832,111353,25238,126558,45888,91419,109834,65487,23584,96697,120863,120677,81632,122799,48443,125723,16397,82284,25119,50794,84437,99215,95120,123627,31690,72803,88153,1596,109361,70725,60350,25538,6866,50489,32833,41297,61486,36337,115295}

    131072

    Returns: 551

  78. {74913,74162,8982,129271,50692,124584,7328,38184,80527,9996,62802,122296,16884,60146,62973,20077,73818,4117,48919,103949,78395,3740,111396,95816,79993,95515,68134,91655,99665,75482,72166,104675,35821,77185,116357,116855,53134,22089,50867,108378}

    131072

    Returns: 469

  79. {127609,252878,106447,133679,130914,198921,9071,130052,98893}

    262144

    Returns: 25

  80. {144059,250194}

    262144

    Returns: 1

  81. {243942,169374,197819,164648,110696,118327,43349,73746,6159,116521,256019,171071,57710,91278,11962,30907,76496,4996,125662,11239,67572,95895,34429,46606,140402,63033,110363,239833,100410}

    262144

    Returns: 245

  82. {126843,220103,35995,115751,142606,203968,87103,71206,129106,246385,41817,16555,18712,81375,105377,68568,104417,81273,213615,96559,154297,163147,724,79813,145748,53779,133962,197398,227362,124704,260717,210449,46927,136472,137634,90632,159813,61872,214005,178409,83125,33239,242594,196130,199731,217205,163443,65258}

    262144

    Returns: 707

  83. {36729,100666,174967,30543,102249,440747,445596,529}

    524288

    Returns: 20

  84. {197847,415218,35993,369402,232391,455198,127005,523038,391348,61067,15892,178362,326103,461728,107300,339614,234631,79960,285209,27787,307315,477513,376846,59995,395296,36329,170249}

    524288

    Returns: 191

  85. {364118,237737,382557,186097,428126}

    524288

    Returns: 7

  86. {269500,272502,155590,251857,340502,201327,365695,516216,483739}

    524288

    Returns: 28

  87. {1039918,1007541,799078,329217,285362,897607,200771,737387,365601,61806,748858,962203,586609,837731,271645,625234,10950,1005442,521877,133153,187394,522817,492110,597162,844376,1030730,652651,486964,303413,398712,800486,671568,298033,601114,137287,663954,396337,817719,759087,891501,1001889,4032,98043,701623,678891}

    1048576

    Returns: 556

  88. {628882,398904,300921,608644,924973,847410,206485,383050,924255,982919,1035016,522422,392313,438993,354089,1005677,584568,1002039,727553,245126,608382,705954,392144,369113,726956,279112,889718,543892,43521,237414,553688,381595,89670,470060,398574,18320,403737,1002224,619634}

    1048576

    Returns: 446

  89. {150029,81051,82748,262098,366830,792472,548961,622293,543181,454662,385946,519605,94867,396979,841580,290155,47389,926044,826932,869675,327425,355520,1040673,253036,978934,20438,79900,533964,508721,912045,12109,70643,601679,740077,438116,94818,740334}

    1048576

    Returns: 379

  90. {43310,302374,495588,326567,547020,352677,440777,753123,190793,948689,402112,670212,731959,677805,903255,968301,1028452,719653,377410,232711,444904,822621,425624,454704,35087,595106,947900,809918,39735,620723,803126,884883,181184,53801,315585,554322,478767,577233,762365,844890,527465,940469,329201,1043936,368219,1005100,721582}

    1048576

    Returns: 644

  91. {937225,2005806,1407927,73149,1239451,1611047,1307681,409504,743848,1933938,650058,1775713,1198304,2012954,1254730,54050,1781438,1648993}

    2097152

    Returns: 98

  92. {995349,1593626,1230711,1292433,404925,1364960,1649060,198517,856871,1535661,1679518,1175720,1849676,330841,1296246,1636045,1687356,1962585,172428,1792183,1673334,126953,1786012,1056026,1371908,1205056,224109,1758866,286444,1724121,726110,1035817,1689190,360088,1478091,30801,952724,156975,957229,890300,1399024,1604137,1123804,1722752,1131329,1038742}

    2097152

    Returns: 595

  93. {102134,996881,828306,1313576}

    2097152

    Returns: 6

  94. {1535592,1856852,1249676,1557055,1339005,1725207,995721,1208711,1945613,1256294,654114,319895,755123,744801,552513,1173593,1471424,1475987,1242880,993832,1997446,769127,52130,1409717,1217643,1992460,1334585,1587357}

    2097152

    Returns: 212

  95. {1379455,3411088,1618568,2969947,2786552,3302523,867454,1716509,2733893,2879175,2897878,2251428,687602,3040125,208284,3262699,2505419,2302143,1865210,2497506,1137248,169479,3634518,1360306,321623,2211209,1160362,3276794,1341486,1500139,1958962,998367,899733,4028175,8606,1520715,922949,1399312,4049688,3397241,1277944,91266,1626755,1144187}

    4194304

    Returns: 614

  96. {1060716,2926138,934414,1346244,1814756,2460064,2075598,3824727,938379,2094688,3364873,3826934,1123082,2726481,1609920,1490341,364039,2403370,1289980,2927353,2535014,392517,2442046,644320,2195452,1304466,1870906,3812583,3598734,1077015,2200504,2656469,750196,2475166,3125951,248520,748867}

    4194304

    Returns: 404

  97. {3730679,1703415,3172942,3570978,1828668,3747074,3652728,3353552,3019363,3261545,1475594,3886602,3477721,1801976,2321290,2631633,3307568,3463803,2671511,3034486,173549,44678,1231548}

    4194304

    Returns: 170

  98. {441741,3884451,1007108,2995620,2397131,4024276,1531297,2385567,3132637,2983130,2713257,1513349,1640550,1053106,714494,4084771,1726858,554969,2269995,1338986,2585696,2519934}

    4194304

    Returns: 130

  99. {8305939,3137280,952234,2366339,732443,2999244,4549181,4117075,5940846,6547426,2942347,1492177,7279457,5450683,3745630,835632,1531506,8208507}

    8388608

    Returns: 95

  100. {5531561,5171652,4653654,2613355,7243680,5587401,1297162,1554126,695349,5449723,2156316,7052171,5506676,2360765,4716641,1113787,7694405,67949,4262033,1892764,7960211}

    8388608

    Returns: 122

  101. {1796869,1630203,4830515,7514535,2266211,3838797,4853204,6520842,6948535,2618692,2258226,94636,4085475,8252278,4152633,5231203,5153301,6060977,6089060,6710672,5193293,7331238,7387855,124357,1948613,8358794,4197346,8306865,1367618,2194579,1781551,2481336,1177687,101149,2599557,4048265,4206446,4122858,4982105,2385370,6867404}

    8388608

    Returns: 465

  102. {7094552,636138,1810228,3569080,2963827,4954464,30056,4855700,8133449,6063905,2626284,6239322,4364440,4605392,6993997,950103,505988,7094347,2345470,5109414,1536459,5311893,1543932,7041136,1693058,2461669,7145964,2165465,3554745,7567825,5840827,2697205,2744637,1104460,14101}

    8388608

    Returns: 358

  103. {7119053,14287261,752505,12451909,4521122,5820880,14576835,16626084,14524644,16775061,16766133,4325276,12908049,353158,4574924,14151463,2151807,4217426,2748295,3470423,9239458,6353638,8302304,5830162,7257937,10331974,1501624,3514578,2097332,1289736}

    16777216

    Returns: 297

  104. {10781110,13062549,16124433,6622627,6205797,3411257,5516021,13212787,9356654,2035053,10851651,11284038,10569701,10411724,8944981,16113515,4201576,14146893,15113247,4460201,12046518,7499130,10652301,4122831,8141264,6562856,772059,12161689,2201156,9570264,1085701,15351459,487331,9646564,13835631,9103961,13836414,644037,13803036,13157513,7882502,11895891,4709353,13473471}

    16777216

    Returns: 501

  105. {7967475,1183008,6086426,893424,15460775,910813,7210719,4317828,13079578,4464695,14021199,10809996,14008102,16730980,6728770,7574769,13155185,9917210,1149638,13353364,9905313,9864397,1750605,4211738,2983622,12004881,3051909,10928526,14619352,15794393,5124420,8273160,4776796,12525188,10334575}

    16777216

    Returns: 366

  106. {1429734,14734400,4262174,7522913,8623465,13447456,2790801,10799091,16075352,8690382,5991446,11072324,12374731,11827293,4906753,13747738,2442618,9237835,10435749,16395735,9276513,14643428,41198,7897977,9727776,7504402,9612881,1272273,5681941,15717405,10344732,1269846,9674448,8435964,5426310,13361199,692100,14548971,6535922,11103706,7969831,3978752,9471586,15005130,7668956,7432545,14858965,12116390}

    16777216

    Returns: 617

  107. {19773622,15134243,9844606,33378627,7370478,26613595,3469565,1638636}

    33554432

    Returns: 21

  108. {27043488,22087465,15503358,29597002,29763010,22672448,17627916,22683877,12320009}

    33554432

    Returns: 26

  109. {25553693,21541161,24569483,20457524,24765341,31427784,26994893,18949760,31919193,14880385,1793846,20131643,7329060,24965427,24584023,13353753,30406266,8289496,14738824,22387080,2568540,21838861,6591775,2839417,1049197,11048690,24572095,27211768,8894121,27866392,11348256,30442470}

    33554432

    Returns: 323

  110. {14807775,32449720,2478602,11070367,1610429,28562371,22830893,7021276,22053,4006621,18678822,3560751,1996769,15697357,30477835,11490903,7923874,7158874,2527289,11567530}

    33554432

    Returns: 112

  111. {19853272,15637820,29430725,18323279,2844922,9127749,13893783,48199454,46509684,50688024,65760679,13807367,14149040,57730926,63431978,35589668,58118888,394936,34697980,45753862,37459349,40752823,29191882,53139071,49378359,44144417,7266375,8655270,48410613,231254,32041192,21158718,23060449,54241754,32148507,39216299,17264050,65965929,26722598,6051864}

    67108864

    Returns: 416

  112. {30241527,5964332,49563934,24594439,27464310,15218838,36413913,14423171,10682751,65601905,9320310,25883269,64489459,7533173,43506709,64902560,6002606,22662072,44716962}

    67108864

    Returns: 111

  113. {37170880,18151615,40239350,34674765,59019131,66283215,64591665,4945998,17111641,48274567,61483741,63425669,43259760,53877015,25224868,54743625,2079532,13884878,28086837,24092650,40490154,34049324,42884773,58810755}

    67108864

    Returns: 156

  114. {15909996,63327384,8447894,60952475,20718065,26078394,39766429,37901672}

    67108864

    Returns: 19

  115. {17009976,57494548,86475229,27328042,94348714,99226918,26279152,82058307,70316328,51015851,52110384,43812990,119620260,87923581,25500295,62110611,114967792,129886964,5471363,14804599,60144873,56592223,22777679,99150249,25570190,7648092,95478915,86384369,67446402,117790109,118509001,89238345}

    134217728

    Returns: 293

  116. {43303685,100995627,62483969,27172167,70937429,25258023,39157698,101745592,81418044,56939587,62145090,102861882,10543802,67457123,80448951,883723,43142758,81688010,88358166,19226112,115074356,110935662,115669982,10691002,115295763,76583876,111765840,97143297}

    134217728

    Returns: 255

  117. {6165852,79340271,11237494,26119604,103768530,9809230,52298855,58938246,10214730,125350848,93558136,70493453,113009312,12011368,106352665,76289456,123534450,65196635,100191157}

    134217728

    Returns: 118

  118. {109148687,33154401,52543579,97289906,119981729,69633141,97156538,47097837,43448216,84910363,36232886,96523310,72990476,128952209,34080265,9033832,17811544,110288590,127297629,81427908,73205039,131723474,124588455,54052151,90859721,31634044,100560145,102123067,114088503,78790192,111594288,55313347,109801220,99882084,23775327,55213934,41515303,69844620}

    134217728

    Returns: 378

  119. {105943640,237149994,180995506,38909092,65164696,138387631,44739566,103291168}

    268435456

    Returns: 19

  120. {102788146,1202339,24122931,244524611,117877353,206668002,11621625,7950024,207786071,107370730,10556309,200740589,37478391,7157681,165576888,46317496,15599830,159322877,117939887,107657008,169536311,259801077,108601335,85321004}

    268435456

    Returns: 162

  121. {152564389,29309264,226683389,159040378,11103438,13103961,43971589,135745177,74965743,263880309,70768946,93345411,79375274,138199492,60221807,83367834,3441502,230871106,11462301,174547126,121559394,105875560,31156735,137404288,181757945,90175856,208110914,190411963,86051124,90030247,120969946,26842218}

    268435456

    Returns: 301

  122. {164861901,158020958,227415929,190908100,27024838,85148754,236997216,123055473,213238772,197838216,250614322,109627957}

    268435456

    Returns: 49

  123. {398176554,57059622,256982307,266969440,433775353,482783526,156367635,497514019,139336049,495499042,404781363,79450256,500603581,409506306,395017340,64928346,409238427,503688170,531705611,345646015}

    536870912

    Returns: 128

  124. {265021955,317739750}

    536870912

    Returns: 1

  125. {447320650,193168844,213220392,63436170,432545492,200329356,521634142,389264142,236296439,62719600,318814848,189011825,320825867,344444831,347849237,141685364,35179880,500546394,313926577,369523978,138853334,40773751,66632622,462738375,330289051,325144565,263743587,223711075,365322948,144777009,424184468,495158308,337030560,181786471}

    536870912

    Returns: 316

  126. {506950375,489033221,462146880,510600011,301221794,239750270,225903966,16012821,167346351}

    536870912

    Returns: 33

  127. {852135703,56637567,224727675,811858731,889023894,958581444,142885678,1029752877,181775959,196013396,940323943,664227883,530832053,656267422,1011117204,586877093,653897299,725856813,297036044,43384396,445685208,909617159,482606157,72200511,75171271,349386732,67685156,1050087617,785670372,72721724,854400917,644150469,218088729,833121131,712731341,978713185,434538092,391077411}

    1073741824

    Returns: 384

  128. {6787612,922662249,610920612,906469917,705763305,309557962,907157059,566589646,681307222,151249257,790645458,861058530,884846718,699304633,887424487,184020319,734571174,427373986,189607035,490003258,17834953,163175570,5186403,511568998,66758251}

    1073741824

    Returns: 209

  129. {77697074,553475423,658034811,101648878,231921420,247329025,850527491,505174193,855427195,1068063192}

    1073741824

    Returns: 36

  130. {863277149,948339776,197473339,366750471,777508755,366594851,620780526,700383108,61530221,587285412,130753252,387890730,979758471,756492790,918031114,120789847,78265137,997323886,462184881,520104674,733814907,1004318889}

    1073741824

    Returns: 130

  131. {585259856,28288008,733258196,382211257,994275488,352461478,463096378,498831595,721825719,897502298,592846586,712786615,179013440,467837479,967722103,78645642,562417864,93971690,780068523,532893795,760461031,741863889,476707525,1048195254,731571767,106964635,629953312,567455857,591086239,454441646,314367303,825052318,627829724,9322530,720236952,617968231,236519631,365528429,416283807,565420604,602128990,475200758,34179847,717668728,27953871,118863245,406154650,588801683,221574849,921701613}

    1073741824

    Returns: 683

  132. {305662802,934481928,464529277,983221821,1035587418,422043293,727850118,688220486,811298814,436948488,920636000,53118474,761236939,767492986,625127352,158767775,261756632,306851108,901101189,12370266,315303346,399077677,759170559,786334253,142519519,508981887,498795040,651990587,29987735,333295371,709287838,1049313067,63217034,915516005,568876460,308317956,591213172,77070760,903817971,455825492,319175209,293814073,391978760,282729448,824222423,362147547,43747035,37386206,834855167,806353287}

    1073741824

    Returns: 718

  133. {1052681926,463672919,97640155,435907888,647234076,834783062,571945811,923814904,371311557,811869151,196633405,516514012,381321127,410079037,741796247,924811936,455458475,542642418,28791139,997624080,398592351,287288665,21892192,458095060,915289315,331978410,750166542,386095407,673461428,224852756,567625932,419161473,766828618,537751943,264498215,89746008,176131646,650894419,493469349,736882368,973461128,967129527,43706065,633551422,401525547,208233906,747308601,844628502,312914142,46338140}

    1073741824

    Returns: 665

  134. {342796717,379309369,214516004,1051514873,164709336,899814804,596798168,384692207,671990275,944931359,386981641,432674125,1000861282,144798426,719297588,675627183,592674614,3733299,975147668,422064988,1034909265,1064185249,394002409,695418033,428301503,89802830,373600475,627025046,315046456,741008468,187564056,448508431,619654022,726085390,707369261,254550320,7941517,239842523,248134752,823839807,879792230,975480485,370828239,871808887,553666131,389772450,1036432854,1053868186,243898665,865445277}

    1073741824

    Returns: 680

  135. {61538191,751012289,37301733,6862722,202799517,907969684,971345221,970934440,226077483,589584122,573100276,1064699404,80103642,349706030,1057078071,870083152,666646808,1048820116,49627789,816238692,592697995,61170090,104126257,743250975,426575377,942767973,178386353,338702249,791996782,579749503,1029278606,511362707,465960064,97202,837261509,1052009631,778063370,542908453,177807141,320724471,681207984,743451510,692641267,958740234,112257677,409842718,58495374,107027187,474137425,361378464}

    1073741824

    Returns: 689

  136. {220148552,959899130,273624055,1043167602,343949528,127598190,860287428,703510487,783539481,1031159285,1048140255,606602346,751245390,991172882,851103031,765215493,6425853,173778624,225172424,48526412,150301520,696391568,707595132,483850674,551841645,656248619,957874369,261481066,139459405,481817965,584115763,990438134,182665691,934382127,435205074,425594032,796408692,935194880,918951599,1020019581,721834691,920630585,207609206,878823580,786608287,499313636,545779362,457711864,176641297,275422319}

    1073741824

    Returns: 672

  137. {828112924,435828285,833507220,272092166,183664509,76714730,766750687,341427796,1071309677,483732902,267581335,324481555,556459045,425112998,755526499,353459474,673898458,892795900,284203763,959673072,807721537,28302082,830868369,688984136,873959845,226637817,731861741,123023994,343075430,7598848,794038472,89802539,361719929,281755803,1002012747,680609470,593389534,1070538101,528184977,542969702,227323437,369548123,504575327,66562922,145265333,121955444,1039392836,537321955,108346708,573661711}

    1073741824

    Returns: 689

  138. {527202888,132793878,795156594,829670923,619131672,346643340,1073690048,349766502,910526413,339479746,110059908,792752773,842671354,164390051,47549178,761054112,181655817,63096970,1034232669,178420555,658818860,887223859,192695932,1055796711,187428820,41561981,753684669,836181282,188959614,249346506,637080851,391119211,788847507,336161057,472460195,894129988,592720564,719398017,1041157306,606312500,453443044,56574461,459918835,679976878,463780448,319646441,1037354469,510939202,52309065,683694906}

    1073741824

    Returns: 663

  139. {402614194,110640012,1046855746,292208760,962435320,9364071,879176144,50365495,763196280,855675309,819554551,312787343,824897134,837635331,1065912150,185083049,590992249,331920226,749447060,564505634,760612328,491899782,871777501,1072377492,1002797886,579720997,874793826,496117670,730408484,967786072,184881693,483096628,679670760,553359108,398948575,957927888,216720794,1026451867,15517768,284663477,823503527,274690974,699951819,71537229,496531779,383290334,183020190,1006938953,133796541,271409962}

    1073741824

    Returns: 725

  140. {563677127,1039522918,331803835,1038876851,543565649,708224239,337458722,683021022,1048461538,208044627,461591751,582610370,208090586,905839116,498063804,516487090,882134297,66097836,529969913,597646285,830671799,1066438047,321969069,196106822,46509463,11527466,645029618,655595455,717599796,923192496,1036250167,275722358,143881800,872841397,21258109,438061746,628368313,211697993,22426414,424859100,1016831501,356704625,357510015,525886096,699245255,132124950,546430458,168856397,356129177,695163462}

    1073741824

    Returns: 720

  141. {505729156,121153464,186902669,484808316,640611244,1030951946,592591819,914053643,941193822,893564617,800059591,1067203518,653829776,85642812,361645586,24330585,447466771,974915705,172065881,972206217,567585887,91046649,319961896,901624506,338259999,112311330,524914635,584454911,118845408,324231373,1064035882,253287322,868388805,77200490,686472863,835257863,236400802,553280168,386113524,863641933,313980649,60821543,946824737,66840466,825384750,352177046,551988265,176284157,1028766136,126319721}

    1073741824

    Returns: 679

  142. {773756463,64449047,333559230,354148007,113512285,718181976,166475543,84936534,768289305,670350689,787462003,807702766,831422285,979473754,267746455,505343535,494792592,955986824,969695628,132129404,477660686,773785720,128374384,218381232,728132941,43902888,1072165905,893473221,165290153,138232602,556305084,181984946,581664482,137321649,470927615,297958332,399509900,10005792,265907445,403041193,746905314,461919069,590953189,387445173,465272511,974898406,746069102,1034049139,131585093,960837417}

    1073741824

    Returns: 677

  143. {574725502,429350086,868527054,316762615,859594319,911568016,669158346,552958696,813188276,492776757,814804693,971875953,361306434,739011254,1068642736,91557440,1804320,374657845,617609236,221350337,430638814,833336157,141468671,693943849,949656305,801625339,373703435,810310719,500970637,737373866,454201679,246797130,956232132,311805170,1067425780,180518862,841476953,7255787,418319289,783980993,1012910566,756720010,59274277,288601730,173313021,1009706870,842859353,916172466,340670211,611665660}

    1073741824

    Returns: 679

  144. {153026472,98190590,219175444,476393122,918339490,915667120,900392500,612061679,225334809,437091071,1066014534,287188536,345655900,805179610,285574912,625877209,65130646,1019713869,260418778,760279173,117232391,703634236,404194479,560367777,199790163,885772545,216463344,5778159,875388177,668376524,194472977,1007243184,279191830,450901221,226499179,56750520,106794754,630738465,652149653,968268187,967492280,132377170,829716540,862466897,938030241,497749676,249740616,771038223,598435951,956216266}

    1073741824

    Returns: 706

  145. {106743440,103722086,426965409,278359315,652002343,467811476,873445480,985601098,907167786,156440712,626396779,107275266,197621716,295507302,593251863,588957442,436633550,784952858,1062325259,427289478,657044375,650040942,1002035505,766319588,597182362,765746917,582027338,700089289,243384130,415893025,961575724,140703317,789993905,178573698,754687645,632610503,895566424,123129031,862017230,528986076,1008266374,368351859,719109707,507387468,428082072,514831222,849317154,482082197,142021306,222586526}

    1073741824

    Returns: 700

  146. {580047368,246891613,808167619,551229120,325116626,101395424,287315033,943557507,672485611,650605774,789253191,693959647,971374780,162959471,255063266,204557406,924875880,136544183,656611357,173932007,438415962,74315720,828362598,283317782,90569421,155081983,555247365,96577339,970763315,636030925,925474748,257244834,553279831,141019690,781399802,568050262,663176314,972318174,314733943,588969792,492444904,248290363,383875449,785314,235610015,271023039,1062005558,330914741,596294650,307531829}

    1073741824

    Returns: 705

  147. {468453370,1873140,669721181,606321454,776934005,760208238,978282554,70153628,856896707,582937054,205980316,206613750,1009373679,598778922,56582673,420509458,554375647,691149548,907579436,298568929,364051000,20920476,506104810,305792461,59517417,162555026,558515757,626303174,958009903,699463714,720996091,854754714,213360643,364473671,654828974,828595629,983110242,954470263,939233011,784746415,1029733907,522073365,816955861,800350902,645985402,243799308,31139260,934652779,836227627,228673464}

    1073741824

    Returns: 706

  148. {30999963,707274309,171778405,163804778,173718596,14376144,454884785,875978987,556634862,487120539,488072891,875878081,398645497,118595936,956281521,838523284,918301372,941110238,1071591838,736268692,150128735,747009183,458247535,1070527219,882136389,807052864,335633169,544718614,736798712,437116502,84089361,743599089,873988534,992937915,48289673,345004722,449353580,516713850,912455697,295156546,1021447137,365000090,486742321,422086359,1064439698,928783158,925804231,859033590,1045153435,508928711}

    1073741824

    Returns: 740

  149. {627829275,322984943,895273688,755436163,146331686,567236772,653480213,1025441929,733671788,1015626543,115297837,900768085,515174553,416630868,669769014,908683323,42466349,469123230,650050911,947476798,1022893201,24354510,772089034,232084768,910262349,757738106,752335267,845635094,347545131,376070384,843520784,119702097,712615435,590667494,504779933,320381439,371451645,956574778,329871357,412474753,989884878,662479747,735225398,315455200,253344768,676784045,878885426,297219071,506228250,252058967}

    1073741824

    Returns: 734

  150. {251580182,694681123,771375900,138199725,720901253,567462973,82670388,854411826,161359220,387962970,739275719,23132533,627747746,501105345,708698013,327407467,677803451,47542035,766965197,598455663,525082638,997817926,10797691,88704163,839951383,62389241,989135637,152557146,181649572,298279794,470163092,55354355,1062295534,172495128,301884188,699891751,450132305,359210346,907840107,156124070,171322857,989388500,815239271,803991536,236773798,902124842,716179385,427958383,1024915709,260031731}

    1073741824

    Returns: 707

  151. {172329500,59070828,195501702,148213340,534247995,881404338,380362400,492233927,566246806,233530577,507267581,758781228,538487704,928064598,323458589,461859660,344839582,725701625,987614234,888370499,1033816027,556782396,850380464,810427106,705926805,733797446,961904461,769283812,751023042,647429956,695430108,315329760,868040898,210198930,881500824,388422626,30116822,574342019,363809572,893602854,737491858,743011623,139754419,668084966,1001914652,435791130,646570521,40372869,624758378,287001238}

    1073741824

    Returns: 720

  152. {487269073,712688697,826353100,787757249,1053935467,170146695,861791607,1015888606,326779314,775520261,713921103,79391493,477250922,670052344,635114114,398224698,1013421888,358920904,453318801,991554247,220264483,858117698,367240128,574378904,13029580,198961518,458981708,766883957,886797579,257246323,36391975,951113586,1057276334,230947657,156929249,102987535,193230307,322290045,158134961,626121383,1065103849,412865748,92972784,1027133180,101428290,362837011,936988586,128061058,670393356,766073606}

    1073741824

    Returns: 722

  153. {386361776,174325037,97076986,731850284,892405989,271849992,985010797,598612897,332870599,554798110,699747900,83209480,796573554,546608963,816905097,62925746,69906715,680537782,325209906,117079630,297892670,165713438,608249103,714054207,486624484,682149896,176249715,583388051,763744945,706875917,266126572,70203857,448336112,551605643,561128588,63514220,551753259,159981199,477970282,669726813,902986718,420656181,454817665,943140814,554739969,1034714444,422306080,779356589,122836435,218928027}

    1073741824

    Returns: 649

  154. {604147701,336997993,955616080,1060230997,673508177,346787154,439582941,435641602,119219828,580687935,200272339,50328011,388182273,236459474,464531461,159211267,840024313,85894300,764629636,892792056,89449169,203950970,336844242,746598695,655599784,575855676,1034743488,734456734,549797736,992760351,409761979,1015086501,626064245,140269112,602725680,254240502,35499521,784489902,903475644,149500452,295410700,898556181,496859058,139719361,1020416106,942931545,944432924,465470248,554976834,307675133}

    1073741824

    Returns: 683

  155. {959183622,253315920,877222267,677208510,251206419,838283411,114706926,512091405,606644206,378680929,509635804,160731987,596632535,519410783,537289178,1062644279,669388569,528614988,399441058,903604989,270489677,862402414,661669954,216726304,66505460,426601933,655819025,851269016,171698772,653718310,297274879,377596681,726496329,817154402,598574743,843724757,1026805115,91097397,648992097,234705556,1030430781,649073178,508650955,856021165,71345794,752915872,605381974,83593734,392966165,846156873}

    1073741824

    Returns: 671

  156. {261556468,628737384,705926664,529617422,761337163,810788179,89697499,389399404,768830074,868187605,452116032,1005734889,221238791,276054031,423350979,1062492996,200636219,246148163,799074702,210170310,756914009,1026680855,660918764,224292081,814921634,639809892,588838246,868923184,60751442,386010758,736633825,500792713,224498181,40661264,625875662,995721412,742542202,344397658,956049133,65895041,845127825,513649057,788994915,92738879,184448035,89123013,636746284,872775389,10777838,921826400}

    1073741824

    Returns: 658

  157. {332644282,64221925,396938718,649182237,656398059,938423029,602913600,395725361,942731646,941302637,180502177,134294249,760307141,492975963,13368891,306113662,607588775,153680712,585936938,64652144,61046666,786237979,972313978,1005539087,193919150,725687295,197101754,766793951,13095892,683437157,968492859,80909386,514544784,32347134,796731164,269812685,297095410,50888036,729718335,898331149,537712145,949784819,811258793,4677833,859665012,162694596,988161128,1056832033,992924799,466668722}

    1073741824

    Returns: 707

  158. {293553073,696748857,163310988,793955895,133896795,161988073,637975806,605398837,5288060,434674596,245439497,749326834,466183228,702945754,772392968,536724270,331456203,1050382651,1035421860,879144177,595966789,405938658,781782450,856487234,797034385,823691073,877527274,109628555,832259025,199273662,411772647,382167261,229514825,27862932,224625382,285714319,490712876,675174630,489887643,701696061,453948693,302576775,332023406,411802104,816238632,774773406,914703288,438335529,859978403,565216456}

    1073741824

    Returns: 701

  159. {274629550,278523656,44548432,375910210,159100477,63525474,224657781,129967360,314339915,531540791,646884162,68663015,522303437,980729040,1000467456,8749939,545443395,314820181,146661766,105705954,656670645,683476468,748305624,537334457,501021022,847396054,39218146,86914251,397013018,1018925601,181740998,307343725,462148063,284732952,1005726214,844730909,281205718,359079819,46269579,111074658,780341440,331359259,385322776,835255666,618097218,923679267,850102184,880953777,619295649,920461313}

    1073741824

    Returns: 821

  160. {512195182,685361423,239098595,294101719,290945389,973739972,926261319,666115412,698872452,503042871,388264130,380596396,429763376,655897627,57430348,213937363,774471426,1051903353,985109222,265080009,338456153,590704768,1063449940,846040665,700943954,805104881,476833074,323247459,550450370,920708583,102693873,602476566,821934887,188919602,620874400,513916459,949769603,746320154,386635018,952660016,564848116,124417099,149710755,721536938,940609315,492813833,72362346,387878010,879685153,699534116}

    1073741824

    Returns: 680

  161. {408024109, 11635919, 196474438, 117649705, 812669700, 553475508, 445349752, 271145432, 730417256, 738416295, 147699711, 880268351, 816031019, 686078705, 1032012284, 182546393, 875376506, 220137366, 906190345, 16216108, 799485093, 715669847, 413196148, 122291044, 777206980, 68706223, 769896725, 212567592, 809746340, 964776169, 928126551, 228208603, 918774366, 352800800, 849040635, 941604920, 326686120, 920977486, 964528038, 659998484, 207195539, 607901477, 725914710, 655525412, 949610052, 142750431, 766838105, 1024818573, 836758851, 97228667 }

    1073741824

    Returns: 720

  162. {438024109, 11635919, 196474438, 117649705, 812669710, 553475508, 445349752, 271145432, 730417256, 738416295, 147699711, 880268351, 816031019, 686079705, 1032012284, 182546393, 875376506, 22013736, 906190345, 16216108, 799485093, 715669847, 413196848, 122291044, 777206980, 68706223, 769896725, 212567592, 809746340, 964776109, 928126551, 228208633, 918774366, 352800800, 849040635, 941604920, 326686120, 920977486, 964528038, 659998814, 207195514, 607901477, 725914710, 655525412, 949610052, 142750431, 766838105, 1024818573, 836758851, 97228691 }

    1073741824

    Returns: 720

  163. {2732, 2839, 324984, 107374182 }

    1073741824

    Returns: 6

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

    1073741824

    Returns: 580

  165. {512, 254, 126, 245, 149, 156, 236, 478 }

    1024

    Returns: 24

  166. {11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111, 11111111 }

    1073741824

    Returns: 0

  167. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 12, 12, 32, 32, 4, 3, 532, 33, 234, 234, 534, 24, 35, 234, 5, 33, 2, 34, 245, 23, 44, 523, 4, 32, 45, 345, 4, 3, 4, 4 }

    1073741824

    Returns: 816

  168. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    16

    Returns: 0

  169. {1, 2, 3, 4 }

    1024

    Returns: 6

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

    16

    Returns: 76

  171. {25633, 2255523, 3, 2263215, 0, 22, 255, 32, 35, 2545, 22566, 22265, 23336, 3225, 3624165, 416245, 64742, 43215, 44545, 4424, 4, 475, 4, 4144, 444, 7, 7, 7, 7, 4, 45, 66, 3358, 3368, 3256, 625, 685, 694, 258, 9543, 6855, 22555, 2555, 25588, 52145, 333, 5165, 55, 553, 555 }

    1073741824

    Returns: 828

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: