Xorspace zestawu liczb jest zbiorem wszystkich liczb, które mogą być uzyskane przez połączenie liczb całkowitych, zaczynające się zwykle operator bitowy XOR ( ^
). Na przykład xorspace (8, 4)
wynosi (0, 4, 8, 12)
: 0 to 4 ^ 4, 12 to 4 ^ 8 i nie można uzyskać innych liczb. Zauważ, że numery początkowe są zawsze uwzględnione w tej definicji (na przykład 4 to 4 ^ 4 ^ 4).
Twoim celem jest napisanie najkrótszego programu, który przyjmuje na wejściu listę liczb całkowitych nieujemnych i wyświetla liczbę elementów w swoim obszarze xorspace.
- Standardowe luki są zabronione.
- Dane wejściowe i wyjściowe mogą mieć dowolny zwykły format . Dane wejściowe są poprawne, niepuste i bez duplikatów.
- Twój kod powinien być w stanie przetworzyć wszystkie przypadki testowe w mniej niż jeden dzień .
Przypadki testowe
Input: 0
Output: 1
Input: 6
Output: 2
Input: 8 4
Ouput: 4
Input: 0 256
Output: 2
Input: 256 259 3
Output: 4
Input: 60 62 94 101 115
Output: 32
Input: 60 62 94 101 115 40 91
Output: 32
Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
Output: 64
Input: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
Output: 32768
l{mxFdy
.y
zastosowane w przypadku od 1 do 63 jest o wiele za wolne. Nie mam pamięci 2 ^ 63.MATL , 11 bajtów
Wypróbuj online!
Ostatni przypadek testowy nie działa w tłumaczu online z powodu ograniczeń pamięci, ale działa offline w mniej niż 2 sekundy na nowoczesnym komputerze.
Wyjaśnienie
W przypadku wprowadzania rozmiaru
n
wykonuje się następujące czynności:n
czasy:Skomentowany kod.
Przykład
Wyniki pośrednie (kroki 2.1 i 2.3) dla danych wejściowych
[256 259 3]
to:Pierwsza iteracja:
[256 259 3]
z[256 259 3]
: obliczenie wszystkich par bitów-XOR daje macierzDołączanie
[256 259 3]
i deduplikacjaDruga iteracja: bieżący wynik
[0 3 259 256]
z[256 259 3]
. Po deduplikacji daje to ponownieTrzecia iteracja: znowu
Tak więc wynikiem jest
4
(liczba wpisów wyniku).źródło
M
. Wielkość wektora wyników pośrednich nigdy nie przekraczaM
, a złożoność wynosi O (M*M
). PO stwierdził, że dokładna definicjan
nie ma znaczenia, jeżeli zdefiniować takn
, jakM
można zastrzeżenia to oznaczać O (n*n
).Haskell , 64 bajty
f
pobiera listę liczb całkowitych i zwraca liczbę całkowitą.Wypróbuj online!
To nie obsługuje pustej listy, ponieważ możesz
$0:
zamiast tego wstawiać spacjęmaximum
.Jak to działa
m
listy wynosi zero, zwraca 1.źródło
Mathematica, 52 bajty
źródło
05AB1E , 8 bajtów
Wypróbuj online!
Wszystkie przypadki testowe kończą się w TIO w czasie krótszym niż 1 minuta.
źródło
2^n
części: /âü^Ùg
dopóki nie zobaczyłem, że możesz xor więcej niż raz, fajne rozwiązanie.Python 2 , 55 bajtów
Wypróbuj online!
Wyróżnia funkcje:
Piękna metoda eliminacji wierszy Ørjan Johansen jest krótsza o jeden bajt.
Python 2 , 54 bajty
Wypróbuj online!
źródło
Galaretka ,
98 bajtówKończy wszystkie przypadki testowe poniżej 8 TIO w czasie krótszym sekund, przy znikomych wymaganiach dotyczących pamięci.
Wypróbuj online!
Jak to działa
źródło
Python, 113 bajtów
źródło
u+=[c][c in s:]
jest równoważne zif
instrukcją.