Statistics

Problem Statement for "OthersXor"

Problem Statement

N wolves are going to challenge bear Limak. Each wolf chooses an integer between 0 and 2^30-1, inclusive, and shows it to all other wolves. No wolf is going to reveal their own number to Limak. Some wolves may remain completely silent, some may give Limak some information. The only information a wolf will tell Limak is the bitwise xor of the numbers of all N-1 other wolves (i.e., all wolves except for the wolf who gives this particular information).


Limak's goal is to find the sum of the numbers chosen by the wolves. If there are multiple sums that are consistent with the information Limak was given, he wants to find the smallest of them.


You are given a int[] x with N elements. Each element of x represents one of the wolves. If x[i] equals -1, wolf i remained silent. Otherwise, wolf i announced that the bitwise xor of the other wolves' numbers is x[i].


If there is at least one sequence of integers between 0 and 2^30-1, inclusive, that is consistent with the information given by the wolves, return the smallest possible sum of such a sequence of numbers. Otherwise, return -1.

Definition

Class:
OthersXor
Method:
minSum
Parameters:
int[]
Returns:
long
Method signature:
long minSum(int[] x)
(be sure your method is public)

Constraints

  • N will be between 2 and 40, inclusive.
  • x will contain exactly N elements.
  • Each element in x will be between -1 and 1073741823 (i.e. 2^30-1), inclusive.

Examples

  1. {1,-1,3}

    Returns: 3

    There are many scenarios that are consistent with this information. For example, it is possible that the wolves chose the numbers {15, 12, 13}. Wolf 0 announces (12 xor 13) = 1, and wolf 2 announces (15 xor 12) = 3. In this case, the sum of the wolves' numbers would be 15+12+13 = 40. However, the sum 40 is not the smallest sum possible. The optimal solution looks as follows: The wolves chose the numbers {2, 1, 0}. Wolf 0 announces (1 xor 0) = 1, and wolf 2 announces (2 xor 1) = 3. The sum in this case is only 2+1+0 = 3, and it can be shown that this is the smallest sum that can be obtained.

  2. {0,0,1}

    Returns: -1

  3. {70,100}

    Returns: 170

    In the only possible scenario wolves choose numbers 100 and 70, resulting in xors 70 and 100.

  4. {-1,0,-1,100,36}

    Returns: 164

  5. {0,536870912,0,536870912,0,536870912,0,536870912,0,536870912, 0,536870912,0,536870912,0,536870912,0,536870912,0,536870912, 1073741823,1073741823,1073741823,123456789,987654321,804289383}

    Returns: 11992352010

  6. {1287325,424244444,92759185,812358213,1000000000,825833522,749092703}

    Returns: -1

  7. {-1,-1}

    Returns: 0

  8. {4564564573,747546456}

    Returns: 1017143733

  9. {1,1,-1}

    Returns: 1

  10. {1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 11

  11. {361358, 86923731, 4389175, 938715, 189725, 41982531, 100000, 195848892, 436912, -1, -1, -1}

    Returns: 537116015

  12. {1,2,3,4,5,6,7,8,123123,4324,342,432,43242,23432,43242,5235,12414,325}

    Returns: 1747415

  13. {143252,435345,242354,5435430,243423,0,4324325,325435,345323,5346435,2342354,5434352,423635,14235,6435435,634435}

    Returns: 74915980

  14. {143252,435345,242354,5435430,243423,0,4324325,325435,345323,5346435,2342354,5434352,423635,14235,6435435,634435,2}

    Returns: -1

  15. {143252,435345,242354,5435430,243423,0,4324325,325435,345323,5346435,2342354,5434352,423635,14235,6435435,634435,-1}

    Returns: 37500481

  16. {143252,435345,242354,5435430,243423,0,4324325,325435,345323,5346435,2342354,5434352,423635,14235,6435435,634435,-1,-1,-1,-1}

    Returns: 37500481

  17. {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: 40

  18. {1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823}

    Returns: 42949672920

  19. {1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823}

    Returns: -1

  20. {1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,-1}

    Returns: 1073741823

  21. {1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,32432452}

    Returns: 2338607451

  22. {1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,1073741823,-1,-1,-1,34543543,0}

    Returns: 3152138383

  23. {304655177,467588829,555675086,891037288,991244276,558090120,357724903,682098056,253751718,817724271,68370721,31811130,1071036550,772324163,495704303,9980291,973896269,383616352,10028830,324097321,795625380,600982224,491488050,685975156,715107627,969101726,194883587,741575237,652839595,9937018,196188000,434229510,754416123,835051397,140094825,618002000,606494155,354857775,516690123,218948990}

    Returns: 21898720216

  24. {117633426,484987471,709580440,53805969,984051029,56514241,384306692,443126512,529698893,288848734,675284202,411074347,7545892,42244721,361521660,1028456646,864347457,578518546,411266510,294415506,315134289,645164599,470063349,98368154,120160810,10999640,801789927,87897166,1047774983,298292781,748244295,126697444,951768108,775865588,91515799,867243410,464518188,463252571,620811551}

    Returns: -1

  25. {344737153,480617257,797203380,913845423,845908070,344556845,926470340,532285346,75601988,378980670,894614367,8003699,638881965,415656359,417925357,217380259,672777087,812584632,771489248,719209913,275413462,352660623,42860163,880811065,399206312,976547634,93127009,44374581,973281342,1060569060,138411148,437521841,209552602,51510399,172880744,-1,493584142,505347102,432185223,1055915587}

    Returns: 17498501173

  26. {1061960561,623588553,717754438,58233048,580198052,508811321,282998242,-1,938531589,792467642,180032997,329824423,621273328,376304131,1023832544,141450388,555670313,402674247,816860531,913520437,231469534,925088031,714220,1005554857,644878583,316921567,143981310,608269287,741282057,544758670,515707169,155904034,1028072290,571771184,119887590,494625831,351958573,383782409,238304981}

    Returns: 19766223905

  27. {174437632,551558970,889620262,579910105,629860972,106140424,159174315,166308318,762539679,187466982,229902159,299855971,890227923,919033521,660576162,130768894,433212095,913102177,356754101,662020707,569642026,785599594,731127054,738614868,258703898,150963210,860081200,154884163,645858156,913081909,781572848,159869793,199765918,406693074,475931741,933890088,349196923,182267427,934236811,157611756}

    Returns: 20092063826

  28. {620633732,281807536,337657226,1043088424,25484948,1033456929,372975537,512124209,552035523,1072384690,751895566,240221623,175395348,39692460,654079815,1058931658,709092279,827605670,67449213,494640206,867075257,317112851,150016522,39963935,526262153,165357274,970633728,181815517,470768008,988841316,743633165,99080502,211587626,930777063,693159428,402702175,627045892,984985072,284684536}

    Returns: 19445705968

  29. {682068009,207845052,799238567,496375601,580943261,815700033,566462509,366140427,988497739,719449479,406421792,438594499,273381693,26873635,953565013,913750481,-1,6997869,165045089,56749138,161653722,185087808,541763617,837012948,282919377,1011641487,1000669078,835176536,786663652,1010646570,937015580,572814356,583136792,149436304,645131426,987402846,413946309,97352690,461533262,903150630}

    Returns: 18631480731

  30. {497176492,541515205,586649362,116784764,867550898,50636911,521083047,365925846,521755373,-1,632056333,687833798,595820530,288522339,823025679,274895996,920508278,182443157,1007555356,732692655,1043589007,548386446,954517372,110804580,74129480,526321691,150647556,36394328,690755626,946718387,1053448914,318188586,677053170,613207681,81875496,103839078,481890677,598132717,885183213}

    Returns: 19514981866

  31. {545987981,80037849,459005957,356253583,708118579,934572441,1025648088,228033023,491855028,776403529,359117867,484915127,1056228968,445258020,1004851402,93992297,876018141,605021877,826099819,658218415,1074280,479650321,31102262,135073916,934317720,751943946,943779492,287139661,963529538,1985493,457326260,1047857542,663095560,753890674,537201318,1017786616,1068656854,909963127,355954462,300372231}

    Returns: 23657339264

  32. {389245589,500855770,96481529,965829334,992620037,773661562,604354753,140840718,240444741,912784707,466839075,396443377,372565146,204302808,643090638,663147107,328680057,483208414,482618653,233325108,432133176,277533394,984453775,923882629,765464686,914564777,940145232,11054273,537218316,4076398,1003474406,874822096,1044931330,802596871,624477501,967652254,1249499,177436924,826103814}

    Returns: 19646665676

  33. {757383361,481598529,555022027,279168388,746258969,617149971,415995073,374451990,511800163,948729722,-1,965067092,697030608,543434933,540842379,594580885,477249285,946918765,500804181,728493370,1036075498,852606470,477460193,1012052960,603168417,1020765593,891144975,425691640,965686220,872230500,878681157,884442543,941084871,1048641845,898437838,578247303,541400876,911231143,1032772764,766078703}

    Returns: 12781694483

  34. {816246976,937488392,477421079,342074283,1007677999,974312296,110741998,68656822,787853560,153733752,548151421,487913622,31948494,981646967,32255555,768946057,852016088,173841907,421348122,578947969,24362570,986816932,960316787,833993385,-1,752744390,1041016008,959748409,310957764,124045612,34267097,449629089,845891615,380635404,951873915,291299810,328786335,914190883,952788326}

    Returns: 18731969440

  35. {906274669,-1,-1,-1,-1,-1,-1,1014741160,-1,-1,-1,-1,-1,-1,-1,-1,372123692,140775107,-1,-1,583620228,-1,-1,9066093,-1,162488606,-1,-1,-1,-1,124499850,586520032,-1,-1,451853092,665644095,-1,878115670,706903298,-1}

    Returns: 6911317756

  36. {-1,353313213,942052590,-1,-1,976296759,-1,341477449,-1,-1,1059412063,-1,-1,894085396,-1,767137519,-1,-1,-1,-1,-1,-1,-1,-1,270817207,-1,-1,230075055,-1,551656359,-1,-1,-1,-1,510919129,545606389,-1,-1,-1}

    Returns: 5474299697

  37. {-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: 0

  38. {-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: 0

  39. {1073741823, 1073741823, 0 }

    Returns: 1073741823

  40. {1, 1, 1 }

    Returns: -1

  41. {0, 1, 1, 1 }

    Returns: 1

  42. {802841382, 534357397, 177754165, -1, 678547788, -1, 688317272, -1, 805157979, -1, 333208725, -1, -1, -1, 612589358, -1, -1, 106762718, 246631849, -1, 651566608, -1, 1022189617, 623136922, -1, -1, 480611944, -1, 67053025, -1, 198671554, -1, -1, 993248132, -1, 219044080, 127973694, -1, -1, -1 }

    Returns: 8909284960

  43. {280945705, 1017306145, 906486313, 838417758, 524047765, 443139872, 370025071, 531410907, 610132713, 127210101, 12550790, 585457629, 567077163, 906560156, 589292786, 738227378, 227517036, 99646123, 217064240, 945664120, 613752033, 59558509, 22079209, 343447238, 589185449, 547200019, 570021376, 1071335415, 939871922, 29206553, 488519058, 147075803, 1046512699, 321263547, 985493562, 496818640, 764403419, 281776809, 1028229547, 300794308 }

    Returns: 21768297226

  44. {-1, 123, -1 }

    Returns: 123

  45. {4, 4, 4, 4, 0 }

    Returns: 4

  46. {-1, 15, 23, 27, 29, 30 }

    Returns: 31

  47. {0, 0, 1, 1, 1, 1, 1, -1 }

    Returns: 3

  48. {-1, 0, -1, 100, 36 }

    Returns: 164

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: