Dengan bilangan bulat , Anda harus menemukan jumlah bit minimum yang perlu dibalik dalam untuk mengubahnya menjadi angka kuadrat . Anda hanya diperbolehkan membalikkan bit di bawah yang paling signifikan .N
Contohnya
- 2 2 0 sudah merupakan angka kuadrat ( ), sehingga output yang diharapkan adalah .
- 11000 → 1100 1 25 = 5 2 1 dapat diubah menjadi angka kuadrat dengan membalik 1 bit: ( ), sehingga output yang diharapkan adalah .
- 23 20 18 30 10110 → 10 0 0 0 16 = 4 2 2 tidak dapat diubah menjadi angka kuadrat dengan membalikkan bit tunggal (hasil yang mungkin adalah , , dan ) tetapi dapat dilakukan dengan membalik 2 bit: ( ), jadi output yang diharapkan adalah .
Aturan
- Tidak apa-apa jika kode Anda terlalu lambat atau melempar kesalahan untuk kasus uji yang lebih besar, tetapi setidaknya mendukung dalam waktu kurang dari 1 menit.
- Ini golf kode !
Uji kasus
Input | Output
----------+--------
4 | 0
22 | 2
24 | 1
30 | 3
94 | 4
831 | 5
832 | 1
1055 | 4
6495 | 6
9999 | 4
40063 | 6
247614 | 7 (smallest N for which the answer is 7)
1049310 | 7 (clear them all!)
7361278 | 8 (smallest N for which the answer is 8)
100048606 | 8 (a bigger "8")
Atau dalam format salin / tempel ramah:
[4,22,24,30,94,831,832,1055,6495,9999,40063,247614,1049310,7361278,100048606]
100048606
pada TIO, apakah itu masalah?Jawaban:
Ruby, 74 byte
Cobalah online!
Ini hanya menghasilkan urutan (yang jauh lebih dari cukup), XOR dengan , dan kemudian mengambil jumlah 1s dalam binernya representasi jika jumlah bit kurang dari atau sama dengan , atau sebaliknya. Kemudian dibutuhkan jumlah bit minimum yang dibalik. Mengembalikan sebagai ganti jumlah bit yang dibalik ketika bit tertinggi yang dibalik lebih besar dari mencegah kasus-kasus ini dipilih sebagai minimum, karena akan selalu lebih besar dari jumlah bit yang dimilikinya. n log 2 nnn log 2 nn[ 12, 22, ... , n2] n log2n n n log2n n
Terima kasih kepada Piccolo untuk menghemat satu byte.
sumber
(n^x*x).to_s 2;...
bukannya(n^x*x).to_s(2);...
Jelly , 12 byte
Cobalah online!
Lihatlah suite tes!
Tautan monadik. Harus golf.
Tapi saya terlalu bodoh untuk memikirkan cara untuk menyingkirkanIni jawaban pertama saya di mana saya berhasil menggunakan penyaringan / pemetaan / perulangan secara umum bersama dengan rantai diad \ o /³
.Penjelasan
sumber
Sekam , 20 byte
Cobalah online!
Penjelasan
sumber
▼mΣfo¬←ṠMz≠ȯfo£İ□ḋπŀ2Lḋ
menghemat 2 byte. RIP Anda skor kuadrat sempurna.Perl 6 , 65 byte
Cobalah online!
Saya merasa sedikit kotor untuk menguji kuadrat sempurna dengan mencari periode dalam representasi string dari akar kuadrat angka, tapi ... apa pun untuk memotong byte.
sumber
05AB1E ,
2015 byte-5 byte terima kasih kepada @ Mr.Xcoder menggunakan port jawaban Jelly-nya .
Cobalah secara online atau verifikasi semua kasus uji (tiga kasus uji terbesar dihapus karena habis waktu setelah 60 detik; masih membutuhkan waktu sekitar 35-45 detik dengan kasus uji lainnya).
Penjelasan:
sumber
Lnʒ‚b€gË}^b€SOß
. Sayangnya, itu merusak test suite AndaJava (JDK 10) , 110 byte
Cobalah online!
sumber
&
bukannya logis dan&&
Gaia , 18 byte
Dekat-port jawaban Jelly saya .
Cobalah online!
Kerusakan
sumber
Brachylog ,
5641 byteItu tidak akan memecahkan catatan panjang tetapi saya pikir saya akan tetap mempostingnya
Cobalah online!
sumber
perakitan x86-64, 37 byte
Bytecode:
Baik, ini menghitung bahkan contoh tertinggi dalam waktu kurang dari satu detik.
Inti dari algoritma ini adalah xor / popcount seperti biasa.
sumber
mov
denganxchg
mov %ecx,%eax
) dan saya tidak bisa membiarkan% ecx mati di sana.Bahasa Wolfram (Mathematica) , 67 byte
Cobalah online!
BitLength
Pick
BitXor
Min
DigitCount
1
sumber
Arang , 31 byte
Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:
sumber
Jelly , 20 byte
Cobalah online!
sumber
Python 2 , 82 byte
Cobalah online!
sumber
Japt
-g
, 20 byteIni bisa di mainkan.
Cobalah online!
sumber
C (gcc) ,
9391 byteCobalah online!
Sunting: Saya pikir solusi asli saya ( Coba online! ) Tidak valid, karena salah satu variabel
m
,, global untuk menyimpan beberapa byte dengan tidak menentukan jenis, diinisialisasi di luarf(n)
dan oleh karena itu harus diinisialisasi ulang di antara panggilanKode tidak dikomentari dan dikomentari:
Suntingan:
sumber