Pod względem koncepcyjnym to wyzwanie jest naprawdę proste. Otrzymałeś listę liczb całkowitych nieujemnych . Jeśli to możliwe, znajdź nieujemną liczbę całkowitą , na przykład, że lista składająca się z jest posortowana. Jeśli takiego nie ma, wynik powinien być czymkolwiek, czego nie można pomylić z prawidłowym , np. Liczbą ujemną, niczym, błędem itp.aiNbi = ai XOR NNN

Oto przykład:

[4, 7, 6, 1, 0, 3]

Jeśli weźmiemy każdy element z tej listy XOR 5, otrzymamy

[1, 2, 3, 4, 5, 6]

który jest posortowany. (Należy pamiętać, że wynikowa lista nie musi mieć unikalnych elementów i nie zawierać żadnych przerw. Jeśli wynik takiej operacji [0, 1, 1, 3]byłby nadal aktualny). Z drugiej strony dla listy

[4, 7, 1, 6, 0, 3]

nie ma takiego N.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Dane wejściowe mogą być w dowolnym dogodnym formacie listy lub ciągu. Możesz założyć, że są one mniejsze niż każdy i że lista zawiera co najmniej jeden element.ai231

Twój kod musi obsłużyć dowolny z przypadków testowych (szczególnie cztery duże) w ciągu kilku sekund.

Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

Dla każdego przypadku testowego, który nie zwraca, -1istnieje nieskończona liczba poprawnych odpowiedzi. Ten wymieniony tutaj jest najmniejszy. Istnieją dodatkowe rozwiązania poprzez dodatkowe ustawienie bitów, które są takie same we wszystkich liczbach całkowitych na wejściu (zwłaszcza tych, które są większe niż najbardziej znaczący bit na największej liczbie listy).

[4 7 6 1 0 3] => 5
[4 7 1 6 0 3] => -1
[0 1 3 4 6 7] => 0
[4 2 3 1] => 6
[2 3 0 0 7 7 4 5 11 11] => 2
[2 3 0 0 7 7 5 4 11 11] => -1
[1086101479 748947367 1767817317 656404978 1818793883 1143500039] => -1
[180522983 1885393660 751646477 367706848 331742205 724919510 850844696 2121330641 869882699 1831158987 542636180 1117249765 823387844 731663826 1762069894 240170102 1020696223 1212052937 2041219958 712044033 195249879 1871889904 1787674355 1849980586 1308879787 1743053674 1496763661 607071669 1987302942 178202560 1666170841 1035995406 75303032 1755269469 200581873 500680130 561748675 1749521426 1828237297 835004548 934883150 38711700 1978960635 209243689 1355970350 546308601 590319412 959613996 1956169400 140411967 112601925 88760619 1977727497 672943813 909069787 318174568 385280382 370710480 809689639 557034312 865578556 217468424 346250334 388513751 717158057 941441272 437016122 196344643 379529969 821549457 97008503 872313181 2105942402 603939495 143590999 1580192283 177939344 853074291 1288703007 1605552664 162070930 1325694479 850975127 681702163 1432762307 1994488829 780869518 4379756 602743458 1963508385 2115219284 1219523498 559301490 4191682 1918142271 169309431 346461371 1619467789 1521741606 1881525154] => -1
[37580156 64423492 87193676 91914964 93632157 96332899 154427982 176139560 184435039 228963836 230164674 279802291 301492375 309127664 345705721 370150824 380319820 403997410 410504675 416543032 418193132 424733526 428149607 435596038 477224208 515649925 519407995 525469350 614538124 624884850 642649261 653488151 679260270 685637235 690613185 739141066 825795124 832026691 832633584 833213619 852655299 913744258 917674993 921902522 925691996 931307936 954676047 972992595 997654606 1020009811 1027484648 1052748108 1071580605 1108881241 1113730139 1122392118 1154042251 1170901568 1180031842 1180186856 1206428383 1214066097 1242934611 1243983997 1244736049 1262979035 1312007069 1312030297 1356274316 1368442960 1377432523 1415342434 1471294243 1529353536 1537868913 1566069818 1610578189 1612277199 1613646498 1639183592 1668015280 1764022840 1784234921 1786654280 1835593744 1849372222 1875931624 1877593764 1899940939 2007896363 2023046907 2030492562 2032619034 2085680072 2085750388 2110824853 2123924948 2131327206 2134927760 2136423634] => 0
[1922985547 1934203179 1883318806 1910889055 1983590560 1965316186 2059139291 2075108931 2067514794 2117429526 2140519185 1659645051 1676816799 1611982084 1736461223 1810643297 1753583499 1767991311 1819386745 1355466982 1349603237 1360540003 1453750157 1461849199 1439893078 1432297529 1431882086 1427078318 1487887679 1484011617 1476718655 1509845392 1496496626 1583530675 1579588643 1609495371 1559139172 1554135669 1549766410 1566844751 1562161307 1561938937 1123551908 1086169529 1093103602 1202377124 1193780708 1148229310 1144649241 1257633250 1247607861 1241535002 1262624219 1288523504 1299222235 840314050 909401445 926048886 886867060 873099939 979662326 963003815 1012918112 1034467235 1026553732 568519178 650996158 647728822 616596108 617472393 614787483 604041145 633043809 678181561 698401105 776651230 325294125 271242551 291800692 389634988 346041163 344959554 345547011 342290228 354762650 442183586 467158857 412090528 532898841 534371187 32464799 21286066 109721665 127458375 192166356 146495963 142507512 167676030 236532616 262832772] => 1927544832
[1922985547 1934203179 1883318806 1910889055 1983590560 1965316186 2059139291 2075108931 2067514794 2117429526 2140519185 1659645051 1676816799 1611982084 1736461223 1810643297 1753583499 1767991311 1819386745 1355466982 1349603237 1360540003 1453750157 1461849199 1439893078 1432297529 1431882086 1427078318 1487887679 1484011617 1476718655 1509845392 1496496626 1583530675 1579588643 1609495371 1559139172 1554135669 1549766410 1566844751 1562161307 1561938937 1123551908 1086169529 1093103602 1202377124 1193780708 1148229310 1144649241 1257633250 1241535002 1247607861 1262624219 1288523504 1299222235 840314050 909401445 926048886 886867060 873099939 979662326 963003815 1012918112 1034467235 1026553732 568519178 650996158 647728822 616596108 617472393 614787483 604041145 633043809 678181561 698401105 776651230 325294125 271242551 291800692 389634988 346041163 344959554 345547011 342290228 354762650 442183586 467158857 412090528 532898841 534371187 32464799 21286066 109721665 127458375 192166356 146495963 142507512 167676030 236532616 262832772] => -1

Wreszcie, oto cztery bardzo duże przypadki testowe, aby upewnić się, że przesyłanie jest wystarczająco wydajne:

• Przypadek testowy 1 powinien ustąpić -1.
• Przypadek testowy 2 powinien ustąpić 0.
• Przypadek testowy 3 powinien ustąpić 1096442624.
• Przypadek testowy 4 powinien ustąpić -1.

Dlaczego ktoś miałby to robić?

Kiedyś przyszło mi do głowy, że operacja XOR może „posortować” tablicę, co umożliwia przeprowadzenie wyszukiwania binarnego na tablicy w O (log n) bez konieczności uprzedniego sortowania. Wydaje się, że możliwe jest określenie Nw czasie pseudoliniowym, co uczyniłoby to szybszą alternatywą dla większości algorytmów sortowania i nie ma wymagań dotyczących pamięci dla sortowania radix. Oczywiście proste liniowe wyszukiwanie w nieposortowanej tablicy będzie szybsze, ale jeśli chcesz przeszukać tę samą tablicę wiele razy, pojedyncze liniowe wstępne obliczenie może znacznie skrócić czas potrzebny na każde wyszukiwanie.

Niestety klasa list, nad którymi to działa, jest raczej ograniczona (mało prawdopodobne jest, aby jednolicie losowe rozkłady dopuszczały N).

Ciekawe pytanie dotyczy tego, czy istnieją inne funkcje bijectywne, które są łatwiejsze do sprawdzenia i / lub mają zastosowanie do szerszej klasy list.

Galaretka, 25 bajtów

ṡ2Zµ^/Bo1Ḅ‘×>/|/H
Ç-¹^Ç¥?

Najnowsze zatwierdzenia stanowią wyzwanie po tym wyzwaniu, ale powyższy kod działa z tą wersją , która go poprzedza. Wypróbuj online!

Aby uruchomić duże przypadki testowe, w zależności od powłoki, konieczne może być owinięcie powyższego kodu w programie, który odczytuje dane wejściowe ze STDIN. Wypróbuj online!

Przypadki testowe

$ xxd -c 13 -g 1 xort-prog.jelly 
0000000: ae 32 5a 8c 5e 2f 42 6f 31 a4 b6 94 3e  .2Z.^/Bo1...>
000000d: 2f 7c 2f 48 0a 92 2d 8e 5e 92 84 3f     /|/H..-.^..?
$ ./jelly f xort-prog.jelly '[4, 7, 6, 1, 0, 3]'; echo
5
$ ./jelly f xort-prog.jelly '[4, 7, 1, 6, 0, 3]'; echo
-1
$ ./jelly f xort-prog.jelly '[0, 1, 3, 4, 6, 7]'; echo
0
$ ./jelly f xort-prog.jelly '[4, 2, 3, 1]'; echo
6
$ ./jelly f xort-prog.jelly '[2, 3, 0, 0, 7, 7, 4, 5, 11, 11]'; echo
2
$ ./jelly f xort-prog.jelly '[2, 3, 0, 0, 7, 7, 5, 4, 11, 11]'; echo
-1
$
$ wget -q http://pastebin.com/raw/{P96PNi79,zCNLMsx9,GFLBXn5b,6F1Yn3gG}
$ xxd -c 14 -g 1 xort-func.jelly 
0000000: ae 32 5a 8c 5e 2f 42 6f 31 a4 b6 94 3e 2f  .2Z.^/Bo1...>/
000000e: 7c 2f 48 0a 92 2d 8e 5e 92 84 3f 0a a0 92  |/H..-.^..?...
$ tr \  , < P96PNi79 | time -f '\n%es' ./jelly f xort-func.jelly
-1
3.69s
$ tr \  , < zCNLMsx9 | time -f '\n%es' ./jelly f xort-func.jelly
0
2.78s
$ tr \  , < GFLBXn5b | time -f '\n%es' ./jelly f xort-func.jelly
1096442624
2.73s
$ tr \  , < 6F1Yn3gG | time -f '\n%es' ./jelly f xort-func.jelly
-1
2.70s

Pomysł

Wykorzystuje to to samo podejście, co odpowiedź @ Jakube , ale moja implementacja jest nieco inna.

Galaretka nie ma jeszcze sortowania, więc obliczamy kandydata do xortowania, XOR wraz z nim listę wejściową, obliczamy kandydata do xortowania z listy XORed i sprawdzamy, czy nowy kandydat ma zero. Jeśli tak, drukujemy pierwszego kandydata; w przeciwnym razie drukujemy -1 .

Ponadto, Jelly wydaje się nie mieć jeszcze rozsądnego sposobu na rzucanie liczb całkowitych (nawet dzielenie liczb całkowitych może zwracać liczby zmiennoprzecinkowe), więc musiałem wymyślić dość kreatywny sposób zaokrąglania listy liczb do następnej potęgi 2 . Zamiast log-floor-pow przekształcam wszystkie liczby całkowite na binarne, zamieniam wszystkie cyfry binarne na 1 , przekształcam z powrotem na liczby całkowite, dodam 1 i dzielę przez 2 .

Kod

ṡ2Zµ^/Bo1Ḅ‘×>/|/H  Helper link. Argument: M (list of integers)

ṡ2                 Yield all overlapping slices of length 2 (pairs) of M.
  Z                Zip to group first and second coordinates.
   µ               Begin a new, monadic chain.
    ^/             XOR the corresponding coordinates.
      B            Convert all results to binary.
       o1          OR (logical) all binary digits with 1.
         Ḅ         Convert back to integer.
          ‘        Increment all integers.
           ×>/     Multiply each rounded (a ^ b) by (a > b).
                   This replaces (a ^ b) with 0 unless a > b.
              |/   OR all results.
                H  Halve the result.

Ç-¹^Ç¥?            Main link. Input: L (list of integers)

Ç                  Call the helper link on L. Result: C (integer)
     ¥             Create a dyadic chain:
   ^                 XOR the elements of L with C.
    Ç                Call the helper link on the result.
      ?            If the result in non-zero:
 -                   Yield -1.
  ¹                Else, yield C.

Pyth, 40 36 31 30 bajtów

Ju.|G^2slHxMf>FT.:Q2Z|tSIxRJQJ

Wypróbuj online: pakiet demonstracyjny lub testowy

Każdy z dużych przypadków testowych kończy się w ciągu kilku sekund.

Wyjaśnienie:

Najpierw wyjaśnię metodę i dlaczego działa. Zrobię to z listy np: [7, 2, 13, 9].

Pierwsze dwie liczby są już niepoprawne ( 7 > 2). Chcemy xor z pewną liczbą, aby zmienić ten symbol nierówności ( 7 xor X < 2 xor X). Ponieważ xor działa na reprezentacjach binarnych, spójrzmy na nie.

7 = 1 1 1
2 =   1 0

Kiedy zastosujemy xor z pewną liczbą do każdej liczby, wartość w niektórych pozycjach ulegnie zmianie. Jeśli zmienisz wartości na pierwszej pozycji ( 2^0), symbol nierówności nie zmieni się. To samo dzieje się, gdy zmieniamy wartości na drugiej pozycji ( 2^1). Również symbol nie ulegnie zmianie, jeżeli zmiana wartości na czwarty, piąty ... stanowiska ( 2^3, 2^4...). Symbol nierówności zmienia kierunek tylko, jeśli zmienimy trzecią pozycję ( 2^2).

7 xor 2^0 = 1 1 0   7 xor 2^1 = 1 0 1   7 xor 2^2 =   1 1   7 xor 2^3 = 1 1 1 1
2 xor 2^0 =   1 1   2 xor 2^1 =     0   2 xor 2^2 = 1 1 0   2 xor 2^3 = 1 0 1 0
     6 > 3               5 > 0               3 < 6               15 > 10

Jeśli zmieniamy wiele pozycji jednocześnie, oczywiście dzieje się to samo. Jeśli którakolwiek z pozycji, które zmieniamy, jest trzecia, to zmienia się symbol nierówności, inaczej nie.

Kolejna para jest już posortowane: 2 < 13. Jeśli spojrzymy na reprezentację binarną, zauważymy, że możemy do niej dodać dowolną wartość, a symbol nierówności jest nadal poprawny, z wyjątkiem sytuacji, gdy zmieniamy czwartą pozycję ( 2^3).

 2 =     1 0    2 xor 2^3 = 1 0 1 0
13 = 1 1 0 1   13 xor 2^3 =   1 0 1
   2 < 13            10 > 5

Nie chcemy więc zmieniać czwartej pozycji. Od następnej pary chcemy coś zmienić 13 > 9. Tutaj znowu musimy zmienić trzecią pozycję.

13 = 1 1 0 1   13 xor 2^2 = 1 0 0 1
 9 = 1 0 0 1    9 xor 2^2 = 1 1 0 1
   13 > 9            9 < 13

Podsumujmy teraz: aby znaleźć się na posortowanej liście, musimy ponownie zmienić trzecią pozycję i nie chcemy zmieniać czwartej pozycji. Wszystkie pozostałe pozycje nie mają znaczenia. Najmniejsza liczba to po prostu 4 = 0100. Inne opcje byłoby 5 = 0101, 6 = 0110, 7 = 0111, 20 = 10100, 21 = 10101, ...

Xoring z 4spowoduje powstanie listy [3, 6, 9, 13], z 6dostanie [1, 4, 11, 15], a z 21dostanie [18, 23, 24, 28].

Tak więc w przypadku listy musimy znaleźć pozycje, które zmienią symbol nierówności, jeśli wskaże niewłaściwy kierunek. Pozycję znajdujemy po prostu biorąc najbardziej znaczący fragment xor z pary. Łączymy wszystkie te pozycje (z lub), aby uzyskać liczbę kandydatów. Sprawdzamy, czy przypadkowo nie zniszczyliśmy już posortowanych par.

Ju.|G^2slHxMf>FT.:Q2Z   implicit: Q = input list
                .:Q2    all substrings of length 2
            f>FT        filter for pairs that are in descending order
          xM            apply xor to each such pair
 u                  Z   reduce this list, start value G = 0
                           iteration value is H
     ^2slH                 2 to the power of floor(logarithm base 2 of H)
                           this gives a mask representing the most significant bit
  .|G                      update G with the bitwise or of G and ^
J                       store the result in J


|tSIxRJQJ   
    xRJQ      xor each element of the input list with J
  SI          check if the list is sorted
 t            subtract 1
|       J     this number or (if equal to zero) J
              implicit print

Ruby 2, 119

->a,*o{a.each_cons(2){|x,y|x==y||o[i=(x^y).bit_length-1]==1-(o[i]=x[i])&&(return-1)};(o.map(&:to_i).reverse*'').to_i 2}

Działa w 42 milisekundach w dużych przypadkach testowych.

Nie golfowany:

def first_differing_bit(a,b)
  (a^b).bit_length - 1
end

def xort(ary)
  required_bits = []
  ary.each_cons(2) do |a,b|
    i = first_differing_bit(a,b)
    if i > -1
      bit = a[i]
      if required_bits[i] && required_bits[i] != bit
        return -1
      else
        required_bits[i] = bit
      end
    end
  end
  required_bits.map(&:to_i).reverse.join.to_i(2)
end

Raz napisałem najpierw wersję bez golfa, a potem grałem w golfa, ponieważ ustalenie właściwego algorytmu było wyzwaniem samym w sobie.

Kilka lat temu próbowałem napisać coś takiego, aby stworzyć strukturę drzewa binarnego, która lokalnie sam się równoważy, pozwalając każdemu węzłu dynamicznie na nowo zdefiniować funkcję porównania. Na początku myślałem, że mogę po prostu użyć XOR, ale jak mówisz dla danych losowych, jest mało prawdopodobne, aby istniała realna wartość.

Julia, 174 144 77 75 71

[EDYCJA] Podziękowania dla Alexa A. za anonimizację i różne skróty.
[EDYCJA 2] Zastąpiłem własną implementację wbudowanym issorted().

Działa w czasie liniowym i obsługuje duże pliki bez zauważalnego opóźnienia. Działa równie dobrze dla liczb ujemnych.

l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])

Kolejny wariant, który oblicza wynik najbliższy danemu kluczowi (powyższy zwraca najmniejszy).

(l,r)->(s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])

stosowanie:

julia> xort = l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])
(anonymous function)

julia> xort([4 7 6 1 0 3])
5

Przykład krok po kroku: [4 7 6 1 0 3] => 5

Start with:
     4  0b0100
     7  0b0111
     6  0b0110
     1  0b0001
     0  0b0000
     3  0b0011
result  0b0000

If the first n bits are sorted, do nothing.
        0b0
        0b0
        0b0
        0b0
        0b0
        0b0
result  0b0000
          ^
If the first n bits are not sorted, flip the nth bit.
        0b01            0b00
        0b01            0b00
        0b01            0b00
        0b00      =>    0b01
        0b00            0b01
        0b00            0b01
result  0b0000          0b0100
           ^               ^
        0b000
        0b001
        0b001
        0b010
        0b010
        0b011
result  0b0100
            ^
        0b0000          0b0001  1
        0b0011          0b0010  2
        0b0010          0b0011  3
        0b0101    =>    0b0100  4
        0b0100          0b0101  5
        0b0111          0b0110  6
result  0b0100          0b0101  5
             ^               ^
If the bit flip does not sort the truncated integers, xorting is
impossible. We continue anyway and check for success in the end.

JavaScript (ES6) 85 97 114 117

Edytuj Usunięto głupie, bezużyteczne ostatnie AND
Edit2 Skrócono wyszukiwanie najlepszych bitów
Edit3 Wow! Odkryłem, że ES6 (prawie) ma wbudowaną funkcję znajdowania górnego bitu (Math.clz32 liczy 0 górnych bitów)

Jest to oparte na rozwiązaniu @Jakube (pls upvote that). Nigdy bym tego nie znalazła.

Idę o krok do przodu, raz iterując listę i trzymając trochę maski z bitami, które trzeba odwrócić, i kolejny z bitami, które trzeba zachować.

Jeśli nakładają się na siebie maski bitów, wówczas żadne rozwiązanie nie jest możliwe, w przeciwnym razie rozwiązaniem jest „bity do odwrócenia”

Ponieważ operacje binarne w javascript działają tylko na 32-bitowych liczbach całkowitych ze znakiem, zwracana wartość to 32-bitowa liczba całkowita ze znakiem, która może być ujemna lub 0.

Jeśli nie ma rozwiązania, zwracana wartość to „X”

l=>l.map(v=>(t=v^p&&1<<(31-Math.clz32(v^p)),v>p?k|=t:c|=t,p=v),p=l[c=k=0])&&c&k?"X":c

Test

Dłuższe testy na jsfiddle

X=l=>l.map(v=>(t=v^p&&1<<(31-Math.clz32(v^p)),v>p?k|=t:c|=t,p=v),p=l[c=k=0])&&c&k?"X":c

console.log=x=>O.textContent+=x+'\n'
;[
[[4,7,6,1,0,3], 5],
[[4,7,1,6,0,3], 'X'],
[[0,1,3,4,6,7], 0],
[[4,2,3,1], 6], 
[[2,3,0,0,7,7,4,5,11,11], 2],
[[2,3,0,0,7,7,5,4,11,11], 'X'],
[[1086101479,748947367,1767817317,656404978,1818793883,1143500039],'X'],
[[180522983,1885393660,751646477,367706848,331742205,724919510,850844696,2121330641,869882699,1831158987,542636180,1117249765,823387844,731663826,1762069894,240170102,1020696223,1212052937,2041219958,712044033,195249879,1871889904,1787674355,1849980586,1308879787,1743053674,1496763661,607071669,1987302942,178202560,1666170841,1035995406,75303032,1755269469,200581873,500680130,561748675,1749521426,1828237297,835004548,934883150,38711700,1978960635,209243689,1355970350,546308601,590319412,959613996,1956169400,140411967,112601925,88760619,1977727497,672943813,909069787,318174568,385280382,370710480,809689639,557034312,865578556,217468424,346250334,388513751,717158057,941441272,437016122,196344643,379529969,821549457,97008503,872313181,2105942402,603939495,143590999,1580192283,177939344,853074291,1288703007,1605552664,162070930,1325694479,850975127,681702163,1432762307,1994488829,780869518,4379756,602743458,1963508385,2115219284,1219523498,559301490,4191682,1918142271,169309431,346461371,1619467789,1521741606,1881525154],'X'],
[[37580156,64423492,87193676,91914964,93632157,96332899,154427982,176139560,184435039,228963836,230164674,279802291,301492375,309127664,345705721,370150824,380319820,403997410,410504675,416543032,418193132,424733526,428149607,435596038,477224208,515649925,519407995,525469350,614538124,624884850,642649261,653488151,679260270,685637235,690613185,739141066,825795124,832026691,832633584,833213619,852655299,913744258,917674993,921902522,925691996,931307936,954676047,972992595,997654606,1020009811,1027484648,1052748108,1071580605,1108881241,1113730139,1122392118,1154042251,1170901568,1180031842,1180186856,1206428383,1214066097,1242934611,1243983997,1244736049,1262979035,1312007069,1312030297,1356274316,1368442960,1377432523,1415342434,1471294243,1529353536,1537868913,1566069818,1610578189,1612277199,1613646498,1639183592,1668015280,1764022840,1784234921,1786654280,1835593744,1849372222,1875931624,1877593764,1899940939,2007896363,2023046907,2030492562,2032619034,2085680072,2085750388,2110824853,2123924948,2131327206,2134927760,2136423634],0],
[[1922985547,1934203179,1883318806,1910889055,1983590560,1965316186,2059139291,2075108931,2067514794,2117429526,2140519185,1659645051,1676816799,1611982084,1736461223,1810643297,1753583499,1767991311,1819386745,1355466982,1349603237,1360540003,1453750157,1461849199,1439893078,1432297529,1431882086,1427078318,1487887679,1484011617,1476718655,1509845392,1496496626,1583530675,1579588643,1609495371,1559139172,1554135669,1549766410,1566844751,1562161307,1561938937,1123551908,1086169529,1093103602,1202377124,1193780708,1148229310,1144649241,1257633250,1247607861,1241535002,1262624219,1288523504,1299222235,840314050,909401445,926048886,886867060,873099939,979662326,963003815,1012918112,1034467235,1026553732,568519178,650996158,647728822,616596108,617472393,614787483,604041145,633043809,678181561,698401105,776651230,325294125,271242551,291800692,389634988,346041163,344959554,345547011,342290228,354762650,442183586,467158857,412090528,532898841,534371187,32464799,21286066,109721665,127458375,192166356,146495963,142507512,167676030,236532616,262832772],1927544832],
[[1922985547,1934203179,1883318806,1910889055,1983590560,1965316186,2059139291,2075108931,2067514794,2117429526,2140519185,1659645051,1676816799,1611982084,1736461223,1810643297,1753583499,1767991311,1819386745,1355466982,1349603237,1360540003,1453750157,1461849199,1439893078,1432297529,1431882086,1427078318,1487887679,1484011617,1476718655,1509845392,1496496626,1583530675,1579588643,1609495371,1559139172,1554135669,1549766410,1566844751,1562161307,1561938937,1123551908,1086169529,1093103602,1202377124,1193780708,1148229310,1144649241,1257633250,1241535002,1247607861,1262624219,1288523504,1299222235,840314050,909401445,926048886,886867060,873099939,979662326,963003815,1012918112,1034467235,1026553732,568519178,650996158,647728822,616596108,617472393,614787483,604041145,633043809,678181561,698401105,776651230,325294125,271242551,291800692,389634988,346041163,344959554,345547011,342290228,354762650,442183586,467158857,412090528,532898841,534371187,32464799,21286066,109721665,127458375,192166356,146495963,142507512,167676030,236532616,262832772],'X']
].forEach(t=>{
  var i=t[0],k=t[1],r=X(i)
  console.log((k==r?'OK ':'Error (expected '+k+') ')+r+' for input '+i)
})

<pre id=O></pre>

ES6, 84 bajty

a=>(i=e=0,a.reduce((x,y)=>(z=1<<31-Math.clz32(x^y),x>y?i|=z:y>x?e|=z:z,y)),i&e?-1:i)

Edycja: Zanim napisałem odpowiedź, algorytm został już opublikowany niezależnie przez @Jakube; mój algorytm jest taki sam, ale to nie był plagiat uczciwy! Zauważyłem też, że od tego czasu została opublikowana inna odpowiedź JavaScript. Przepraszam, jeśli nadepnę na czyjeś palce.

Edycja: Zapisano 8 bajtów dzięki edc65.

C, 144 bajty

#include <strings.h>
#include <stdio.h>
m[2],l,i;main(v){while(scanf("%d",&v)==1)m[l<v]|=(i++&&v^l)<<~-fls(v^l),l=v;printf("%d",*m&m[1]?-1:*m);}

Jest to prawie standardowy C99 (brakuje kilku intspecyfikacji i ma 1 argument za main). Opiera się również na 0<<-1byciu 0 (co wydaje się być prawdą, jeśli kompiluje się go przynajmniej z Clangiem - nie testowałem innych)

Wziąłem metodę Jakube i przeniosłem ją do C. Myślę, że w przypadku C. jest zaskakująco dobrze pod względem wielkości. Jest również super szybki (0,061s, aby uruchomić wszystkie pliki testowe, w tym masywne 4). Pobiera dane wejściowe ze STDIN i wypisze pasującą wartość lub -1 do STDOUT, więc uruchom go z jednym z:

echo "4 7 6 1 0 0 3" | ./xort
./xort < file.txt

Awaria:

// Globals initialise to 0
m[2],                                    // Stores our bit masks
                                         // (m[0]=CHANGE, m[1]=MUST NOT CHANGE)
l,                                       // Last value
i;                                       // Current iteration
main(v){
    while(scanf("%d",&v)==1)             // Read each value in turn
        m[l<v]|=                         // If they are sorted, we mark a bit as
                                         // MUST NOT CHANGE (m[1]), otherwise we
                                         // mark as CHANGE (m[0])
                (i++&&v^l)               // If this is the first iteration,
                                         // or the value is unchanged, mark nothing
                          <<~-fls(v^l),  // Mark the highest bit which has changed
                                         // = (1<<(fls(v^l)-1)
        l=v;                             // Update last value
    printf("%d",
                *m&m[1]                  // Check if result is valid (if any bits
                                         // are both MUST NOT CHANGE and CHANGE,
                                         // it is not valid)
                       ?-1               // Print -1 on failure
                          :*m);          // Print value on success
}

Julia, 124 bajty

f(x,g=0)=issorted(([g|=2^Int(log2(h)÷1)for h=map(k->k[1]$k[2],filter(j->j[1]>=j[2],[x[i-1:i]for i=2:endof(x)]))];g)$x)?g:-1

Jest to funkcja, która akceptuje tablicę liczb całkowitych i zwraca liczbę całkowitą. Wykorzystuje podejście Jakube .

Nie golfowany:

function f{T<:Integer}(x::Array{T,1}, g::T=0)
    # Get all pairs of elements in the input array
    pairs = [x[i-1:i] for i = 2:endof(x)]

    # Filter to pairs in descending order
    desc = filter(j -> j[1] ≥ j[2], pairs)

    # Map XOR over these pairs
    xord = map(k -> k[1] $ k[2], desc)

    # For each element of this array, update the
    # parameter g (which defaults to 0) as the
    # bitwise OR of itself and 2^floor(log2(element))
    for h in xord
        g |= 2^Int(log2(h) ÷ 1)
    end

    # If the array constructed as g XOR the input is
    # sorted, we've found our answer! Otherwise -1.
    return issorted(g $ x) ? g : -1
end

Python 2, 204 bajty

def f(a):
 m=n=0
 for i in range(32):
  b=2**(31-i);m|=b
  for n in[n,n|b]:
   if not q(a,m,n):break
  else:return-1
 return n
def q(a,m,n):
 if a:p=a[0]&m^n
 for t in a:
  t=t&m^n
  if t<p:return 1
  p=t

Dane wejściowe są przekazywane jako lista do funkcji f.

Ten kod oblicza wartość N (nazwaną n w programie) po jednym bicie, zaczynając od najbardziej znaczącego bitu. (pętla „for i”)

Dla każdej pozycji bitu pętla „for n” najpierw próbuje użyć 0 dla tego bitu n. Jeśli to nie działa, próbuje użyć 1. Jeśli żadne z tych nie działa, nie ma rozwiązania. Zauważ, że klauzula else znajduje się w pętli „for n”, a nie w instrukcji if. W Pythonie instrukcja for może mieć klauzulę else, która jest wykonywana po zakończeniu pętli, ale nie jest wykonywana, jeśli wyjdziemy z pętli.

Funkcja q sprawdza, czy występują problemy z kolejnością na liście, biorąc pod uwagę listę (a), maskę bitową (m) i wartość, którą należy zapisać przy każdej wartości na liście (n). Zwraca 1, jeśli występuje problem z zamówieniem, lub Brak, jeśli zamówienie jest prawidłowe. Brak jest domyślną wartością zwracaną, więc zapisałem mi kilka znaków.

Ten kod poprawnie obsługuje pustą listę lub listę z 1 elementem, zwracając 0. „Jeśli a:” w funkcji q istnieje tylko po to, aby uniknąć wyjątku IndexError, gdy lista jest pusta. Zatem 5 dodatkowych bajtów można usunąć, jeśli obsługa pustych list nie jest wymagana.

Na moim komputerze duży przypadek testowy nr 3 zajął 0,262 sekundy. # 2 zajął mniej więcej to samo. Wszystkie przypadki testowe łącznie trwały 0,765 sekundy.

CJam, 37 bajtów

q~_2ew{:>},{:^2mLi2\#}%0+:|_@f^_$=\W?

Sprawdź to tutaj.

Wykorzystuje ten sam algorytm, co kilka innych odpowiedzi. Jest to zasadniczo moja referencyjna implementacja, której użyłem do stworzenia przypadków testowych. Jednak ukradłem sztuczkę Jakube'a polegającą na sprawdzeniu tylko par obrażających się i po prostu wypróbowaniu wyniku w pewien sposób. To łamie pseudoliniowość, ale O (n log n) jest wciąż wystarczająco szybkie dla przypadków testowych. Mój oryginalny kod sprawdził również pary, które są już w porządku, i utworzyłem listę bitów, których nie można przełączać w celu zachowania ich względnej kolejności, i na końcu sprawdziłem, czy między dwiema maskami bitowymi nie nakładają się. Algorytm ten został pierwotnie zasugerowany przez Bena Jacksona .

Python 2, 226 214 bajtów

Prosty algorytm, zbudowany wczoraj, grał dzisiaj w golfa.

o=input()
s=sorted
p=s(set(o),key=o.index)
n=q=0
while 1:
 a=1
 while 1-q and p[0]<p[1]:p=p[1:];q=len(p)==1
 if q:break
 while not p[0]^a<p[1]^a:a*=2
 n+=a;p=[i^a for i in p]
t=[a^n for a in o]
print[-1,n][s(t)==t]

Nie golfowany:

def xor(a,b): return a^b

def rm_dupes(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

def rm_sorted(seq):
    while seq[0] < seq[1]:
        seq = seq[1:]
        if len(seq) == 1: return seq
    return seq

inp = input()
oi = inp

inp = rm_dupes(inp)
n=0
old_inp=0
while old_inp != inp:
    old_inp = inp
    inp = rm_sorted(inp)
    if len(inp)==1:break
    highest_set0 = len(bin(inp[0]))-3 # bin returns in form 0bxxx
    highest_set1 = len(bin(inp[1]))-3 # bin returns in form 0bxxx
    if highest_set1 == 0:
        try:
            t0 = max(int(bin(inp[0])[3:], 2), 1)
        except ValueError: toggle_amount = 1
        else: toggle_amount = t0^inp[0]
    else:
        fallen = False
        for i in xrange(max(highest_set0,highest_set1)+1):
            toggle_amount = 2**i
            if inp[0]^toggle_amount < inp[1]^toggle_amount:
                fallen = True
                break
        assert(fallen)
    n+=toggle_amount
    inp = [i^toggle_amount for i in inp]

out=map(xor, oi, [n]*len(oi))
if sorted(out)==out :print n
else:print -1

C, 312 bajtów

#define R return
t,i,*b;f(int*a,int l,int k){int s=a[0]>>k&1,j=-1,i=1;if(k<0)R 0;for(;i<l;++i){t=a[i]>>k&1;if(s!=t)if(j<0)j=i,s=t;else R 1;}if(j<0)R f(a,l,k-1);else{if(s+b[k]==2)R 1;b[k]=s+1;R f(a,j,--k)||f(a+j,l-j,k);}}h(int*a,int l){int c[32]={0};b=c;if(f(a,l,30))R -1;t=0;for(i=0;i<32;++i)t|=(b[i]&1)<<i;R t;}

Definiuje funkcję h(int*a,int l)przenoszącą wskaźnik do tablicy i jej długość. Oto behemot programu testowego.

Nieznacznie nie golfista:

int t, i, *b;

int f(int * a, int l, int k) {
    int s = a[0] >> k & 1;
    int j = -1;
    int i = 1;
    if (k < 0) return 0;
    for (; i < l; ++i) {
        t = a[i] >> k & 1;
        if (s != t) {
            if (j < 0) {
                j = i;
                s = t;
            } else return 1;
        }
    }
    if (j < 0) {
        return f(a, l, k - 1);
    } else {
        if (s + b[k] == 2) return 1;
        b[k] = s + 1;
        return f(a, j, --k) || f(a + j, l - j, k);
    }
}

int h(int * a, int l) {
    int c[32] = {0};
    b = c;
    if (f(a, l, 30)) return -1;
    t = 0;
    for (i = 0; i < 32; ++i) {
        t |= (b[i] & 1) << i;
    }
    return t;
}

Mathematica, 99 97 znaków

Podziękowania dla Martina Büttnera za porady.

x@l_:=If[OrderedQ[l~BitXor~#],#,-1]&@Fold[#+#2Boole@!OrderedQ@⌊l~BitXor~#/#2⌋&,0,2^32/2^Range@32]

Wyjaśnienie:

Zrobimy wiele prób modyfikacji, Nzaczynając od zera, i przeprowadzimy test, aby zweryfikować kandydata N.

Krok 1. Dostajemy te numery (32-bitowe liczby całkowite) „xor” ed przez N( = 0teraz) i podzielona przez 2^31: ⌊l~BitXor~#/#2⌋. Istnieją trzy przypadki:

• zamówione, np . {0, 0, 1, 1, 1, 1, 1, 1};
• można skorygować, np {1, 1, 1, 1, 0, 0, 0, 0};
• inaczej, np {0, 0, 1, 0, 0, 1, 1, 1}.

My nic zrobić, aby Nw pierwszym przypadku, albo dodać 2^31do Nskorygowania zamówienie na drugim przypadku: #+#2Boole@!OrderedQ@.... Natomiast w trzecim przypadku, niemożliwe jest xorting listę cokolwiek robimy, więc po prostu dodać 2^31do Nprostoty (lub cokolwiek!).

Krok 2. Otrzymujemy te liczby „xor” Ni podzielone przez 2^30. Są jeszcze trzy przypadki:

• zamówione, np . {0, 1, 2, 2, 2, 2, 3, 3};
• można skorygować, np {1, 1 , 0, 0, 3, 2, 2, 2};
• inaczej, np {3, 3, 1, 3, 2, 0, 1, 0}.

My nic zrobić, aby Nw pierwszym przypadku, albo dodać 2^30do Nskorygowania zamówienie na drugim przypadku. W przeciwnym razie, zdajemy sobie sprawę, że xorting jest niemożliwe, więc po prostu dodać 2^30do Nprostoty ponownie.

Krok 3 ~ 32. Mamy rekurencyjnie dostać te numery „xor” ed przez Ni podzielona przez 2^29, 2^28, ..., 2^0. I rób podobne rzeczy:Fold[...,0,2^32/2^Range[32]]

Krok 33. Teraz w końcu mamy kandydata N. If[OrderedQ[l~BitXor~#],#,-1]&służy do sprawdzenia, czy Nrzeczywiście przekreśla listę. Jeśli lista może być przez niektórych przekreślona N, nietrudno udowodnić, że zawsze napotkamy pierwszy lub drugi przypadek.

Perl 6 , 79 bajtów

Gdyby nie było limitu czasu, prawdopodobnie byłby to najkrótszy kod Perla 6

{first {[<=] $_ X+^@_},^2*.max} # 31 bytes

Zamiast tego muszę zrobić coś bardziej sprytnego.
Ponieważ wróciłem do tego czasu, była już odpowiedź, która opisuje dobry algorytm i jego uzasadnienie.

{$/=0;for @_.rotor(2=>-1) ->(\a,\b){b>=a or$/+|=2**msb a+^b};$/if [<=] $/X+^@_} # 79

{
  # cheat by using a special variable
  # so there is no need to declare it
  $/=0;

  # takes the elements two at a time, backing up one
  for @_.rotor(2=>-1)
    # since that is a non-flat list, desugar each element into 2
    # terms
    ->(\a,\b){
      # if they are not sorted
      b>=a or
      # take the most significant bit of xoring the two values
      # and numeric or ｢+|｣ it into ｢$/｣
      $/+|=2**msb a+^b
    };


  # returns ｢$/｣ if the list is Xorted
  # otherwise returns Empty
  $/if [<=] $/X+^@_

  # ｢ $/ X[+^] @_ ｣
  # does numeric xor ｢+^｣ between ｢$/｣
  # and each element of the original list ｢@_｣
}

Stosowanie:

# give it a lexical name for ease of use
my &code = {...}

say code [8,4,3,2,1];     # 15

say code [4,7,6,1,0,3]; # 5
say code [4,7,1,6,0,3]; # ()
say code [0,1,3,4,6,7]; # 0
say code [4,2,3,1];     # 6
say code [2,3,0,0,7,7,4,5,11,11]; # 2
say code [2,3,0,0,7,7,5,4,11,11]; # ()
say code [1086101479,748947367,1767817317,656404978,1818793883,1143500039]; # ()

# the example files
for 'testfiles'.IO.dir.sort».comb(/«\d+»/) {
  printf "%10s in %5.2f secs\n", code( @$_ ).gist, now - ENTER now;
}
#         () in  9.99 secs
#          0 in 11.70 secs
# 1096442624 in 13.54 secs
#         () in 11.44 secs

Mathematica 650 415 194 bajtów

To wyzwanie pomogło mi zrozumieć trochę o Xortym, o czym nigdy nie myślałem. Zabranie kodu zajęło dużo czasu, ale było warte wysiłku.

BitXordziała bezpośrednio na podstawie 10 liczb. To znacznie zmniejszyło kod z wcześniejszych wersji.

Logika jest prosta. Jeden działa, nie z parami liczb (jak niektóre zgłoszenia), ale raczej z pełnym zestawem liczb po BitXoredycji za pomocą bieżącego „klucza”.

Zacznij od wstępnego rozwiązania lub „klucza” zerowego, to znaczy, że wszystkie bity są zerowe. Gdy oryginalne nliczby są BitXoredytowane z zerem, są zwracane bez zmian. Skoreluj kolejność liczb z zakresem 1, 2, ...n, który reprezentuje idealnie uporządkowaną listę. Korelacja o wartości od -1 do 1 odzwierciedla stopień uporządkowania liczb.

Następnie ustaw bit hi, uzyskaj nowy klucz i BitXorklucz z bieżącym zestawem liczb. Jeśli korelacja między nową sekwencją liczb a idealnie uporządkowaną listą jest poprawą, utrzymuj bit. Jeśli nie, pozostaw bit nieuzbrojony.

Postępuj w ten sposób od hi do niskiego bitu. Jeśli najlepsza korelacja wynosi 1, kluczem jest rozwiązanie. Jeśli nie, wynosi -1.

Istnieją sposoby na zwiększenie wydajności kodu, na przykład poprzez przerwanie procesu natychmiast po znalezieniu rozwiązania, ale wymagałoby to więcej kodowania, a obecne podejście jest bardzo szybkie. (Ostatni i najdłuższy przypadek testowy zajmuje 20 ms.)

c@i_:=Correlation[Ordering@i,Range[Length[i]]]//N;
t@{i_,k_,b_,w_}:=(v= c@BitXor[i,m=k+2^(b-1)];{i,If[v>w,m,k],b-1,v~Max~w})
g@i_:= (If[#4==1,#2,-1] &@@Nest[t,{i,0,b=1+Floor@Log[2,Max@i],x=c@i},b])

g[{4, 7, 6, 1, 0, 3}]

5

g[{4, 7, 1, 6, 0, 3}]

-1

g2@{0, 1, 3, 4, 6, 7}

0

g@{1922985547, 1934203179, 1883318806, 1910889055, 1983590560, 1965316186,2059139291, 2075108931, 2067514794, 2117429526, 2140519185, 1659645051, 1676816799, 1611982084, 1736461223, 1810643297, 1753583499, 1767991311, 1819386745, 1355466982, 1349603237, 1360540003, 1453750157, 1461849199, 1439893078, 1432297529, 1431882086, 1427078318, 1487887679, 1484011617, 1476718655, 1509845392, 1496496626, 1583530675, 1579588643, 1609495371, 1559139172, 1554135669, 1549766410, 1566844751, 1562161307,1561938937, 1123551908, 1086169529, 1093103602, 1202377124, 1193780708, 1148229310, 1144649241, 1257633250, 1247607861, 1241535002, 1262624219, 1288523504, 1299222235,840314050, 909401445, 926048886, 886867060, 873099939, 979662326,963003815, 1012918112, 1034467235, 1026553732, 568519178, 650996158,647728822, 616596108, 617472393, 614787483, 604041145, 633043809, 678181561, 698401105, 776651230, 325294125, 271242551, 291800692, 389634988, 346041163, 344959554, 345547011, 342290228, 354762650, 442183586, 467158857, 412090528, 532898841, 534371187, 32464799, 21286066, 109721665, 127458375, 192166356, 146495963, 142507512, 167676030, 236532616, 262832772}

1927544832

Dodaj ++ , 125 119 bajtów

D,g,@@,BxBBBDbU1€oB]BJ2$Bb1+
D,j,@,bUBSVcGbU£{g}B]BkAbUBSVcGbU£>B]BKBcB*¦Bo2/i
L!,B#a=
D,f,?!,{j}Vad{j}BF€Bx1]G$0=-1$Qp

Wypróbuj online!

_{Jestem naprawdę dumny, że Add ++ jest w stanie to zrobić i nie jest to najdłuższe rozwiązanie tutaj}

Deklaruje funkcję, fktóra bierze każdy element jako osobny argument (np. $f>4>2>3>1)

Jak to działa

Zapnijcie ludzi, to będzie długa jazda

D,g,@@,		; Declare a function 'g'
		; Example arguments: 		[4 7]
	Bx	; Xor;			STACK = [3]
	BB	; To binary;		STACK = [11]
	BD	; Digits;		STACK = [[1 1]]
	bU	; Unpack;		STACK = [1 1]
	1€o	; Replace 0s with 1s;	STACK = [1 1]
	B]	; Wrap;			STACK = [[1 1]]
	BJ	; Concatenate;		STACK = ['11']
	2$Bb	; From binary;		STACK = [3]
	1+	; Increment;		STACK = [4]
		;			Return   4

D,j,@,		; Declare a function 'j'
		; Example argument:		[[4 7 6 1 0 3]]
	bU	; Unpack;		STACK = [4 7 6 1 0 3]
	BS	; Overlapping pairs;	STACK = [4 7 6 1 0 3 [[4 7] [4 6] [6 1] [1 0] [0 3]]]
	VcG	; Keep first element;	STACK = [[[4 7] [4 6] [6 1] [1 0] [0 3]]]
	bU	; Unpack;		STACK = [[4 7] [4 6] [6 1] [1 0] [0 3]]
	£{g}	; Apply 'g' over each;	STACK = [4 2 8 2 4]
	B]	; Wrap;			STACK = [[4 2 8 2 4]]
	Bk	; Global save;		STACK = []		; GLOBAL = [4 2 8 2 4]
	A	; Push arguments;	STACK = [[4 7 6 1 0 3]]
	bU	; Unpack;		STACK = [4 7 6 1 0 3]
	BSVcGbU	; Overlapping pairs;	STACK = [[4 7] [4 6] [6 1] [1 0] [0 3]]
	£>	; Greater than each;	STACK = [0 1 1 1 0]
	B]	; Wrap;			STACK = [[0 1 1 1 0]]
	BK	; Global get;		STACK = [[0 1 1 1 0] [4 2 8 2 4]]
	BcB*	; Products;		STACK = [[0 2 8 2 0]]
	¦Bo	; Reduce by logical OR;	STACK = [10]
	2/i	; Halve;		STACK = [5]
		;			Return   5

L!,		; Declare 'lambda 1'
		; Example argument:		[[1 2 3 4 5]]
	B#	; Sort;			STACK = [[1 2 3 4 5]]
	a=	; Equal to argument;	STACK = [1]
		; 			Return   1

D,f,?!,		; Declare a function 'f'
		; Example arguments:		[[4 7 6 1 0 3]]
	{j}	; Call 'j';		STACK = [5]
	V	; Save;			STACK = []		; REGISTER = 5
	ad	; Push arguments twice;	STACK = [[4 7 6 1 0 3] [4 7 6 1 0 3]]
	{j}	; Call 'j';		STACK = [[4 7 6 1 0 3] 5]
	BF	; Flatten;		STACK = [4 7 6 1 0 3 5]
	€Bx	; Xor each with 5;	STACK = [1 2 3 4 5 6]
	1]	; Call 'lambda 1';	STACK = [1]
	G$	; Retrieve REGISTER;	STACK = [5 1]
	0=	; If equal to 0:
	-1$Q	;   Return -1
	p	; Else, pop condition;	STACK = [5]
		;			Return   5

Stax , 29 bajtów

¬√▬ⁿ{j╔■α√ï(íP♫_z(.▀ng▒JU↨@b┬

Uruchom i debuguj online!

Wykorzystuje rozwiązanie @ RainerP. (Wymyślił część z bitem przerzucającym niezależnie, ale używa tej 32rrczęści)

Złożoność czasowa liniowa.

Używa rozpakowanej wersji do wyjaśnienia.

32rr{|2Y;{y/m:^!c{,{y|^m~}Mm,:^ud:b
32rr                                   Range [32,31..0]
    {                      m           Map each number `k` in the range with
     |2Y                                   `2^k`
        ;{y/m                              Map each number `l` in the input to `floor(l/2^k)`
             :^!                           The mapped array is not non-decreasing
                                           This is the binary digit `l` is mapped to
                c{       }M                If that's true, do
                  ,{y|^m~                  Flip the corresponding bit of every element in the input
                            ,:^        The final array is sorted
                               ud      Take inverse and discard, if the final array is not sorted this results in zero-division error
                                 :b    Convert mapped binary to integer