The xorspace dari himpunan bilangan bulat adalah himpunan semua bilangan bulat yang bisa diperoleh dengan menggabungkan bilangan bulat dimulai dengan operator bitwise XOR biasa ( ^
). Sebagai contoh, xorspace dari (8, 4)
adalah (0, 4, 8, 12)
: 0 adalah 4 ^ 4, 12 adalah 4 ^ 8, dan tidak ada nomor lain yang dapat dihubungi. Perhatikan bahwa angka awal selalu dimasukkan, dengan definisi ini (misalnya, 4 adalah 4 ^ 4 ^ 4).
Tujuan Anda adalah menulis program terpendek yang mengambil daftar bilangan bulat non-negatif sebagai input, dan menampilkan jumlah elemen di xorspace mereka.
- Celah standar dilarang.
- Input dan output dapat dalam format yang biasa . Masukan dijamin valid, tidak kosong, dan tanpa duplikat.
- Kode Anda harus dapat memproses semua kasus uji dalam waktu kurang dari sehari .
Uji kasus
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
diterapkan pada kasus uji 1 hingga 63 terlalu lambat. Saya tidak memiliki memori 2 ^ 63.MATL , 11 byte
Cobalah online!
Kasing uji terakhir tidak berjalan pada juru bahasa online karena keterbatasan memori, tetapi beroperasi offline dalam waktu kurang dari 2 detik pada komputer modern.
Penjelasan
Untuk input ukuran
n
, ini melakukan hal berikut:n
kali:Kode yang dikomentari.
Contoh
Hasil antara (langkah 2.1 dan 2.3) untuk input
[256 259 3]
adalah:Iterasi pertama:
[256 259 3]
dengan[256 259 3]
: menghitung semua pasangan bitwise-XOR menghasilkan matriksMelampirkan
[256 259 3]
dan mendeduplikasiIterasi kedua: hasil saat ini
[0 3 259 256]
dengan[256 259 3]
. Setelah deduplicating ini memberi lagiIterasi ketiga: lagi
Jadi outputnya adalah
4
(jumlah entri hasil).sumber
M
. Jadi ukuran vektor hasil antara tidak pernah melebihiM
, dan kompleksitasnya adalah O (M*M
). OP telah mengatakan bahwa definisi yang tepat darin
tidak masalah, jadi jika saya mendefinisikann
sebagaiM
saya dapat mengklaim ini sebagai O (n*n
).Haskell , 64 byte
f
mengambil daftar bilangan bulat dan mengembalikan bilangan bulat.Cobalah online!
Ini tidak menangani daftar kosong, untuk itu Anda bisa tetapi
$0:
bukan ruang setelahmaximum
.Bagaimana itu bekerja
m
daftar adalah nol, mengembalikan 1.sumber
Mathematica, 52 byte
sumber
05AB1E , 8 byte
Cobalah online!
Semua uji kasus selesai dalam waktu kurang dari 1 menit pada TIO.
sumber
2^n
bagian: /âü^Ùg
sampai aku melihatmu bisa lebih dari sekali, solusi yang bagus.Python 2 , 55 byte
Cobalah online!
Mematikan fungsi:
Metode penghapusan baris indah Ørjan Johansen adalah satu byte lebih pendek.
Python 2 , 54 byte
Cobalah online!
sumber
Jelly ,
98 byteSelesaikan semua kasus uji dalam waktu kurang dari 8 detik pada TIO, dengan persyaratan memori yang dapat diabaikan.
Cobalah online!
Bagaimana itu bekerja
sumber
Python, 113 byte
sumber
u+=[c][c in s:]
yang setara denganif
pernyataan Anda .