Kami mendefinisikan fungsi g sebagai g (n) = n XOR (n * 2) untuk bilangan bulat apa pun n> 0 .
Diberikan x> 0 , temukan bilangan bulat terkecil y> 0 sedemikian sehingga g k (y) = x untuk beberapa k> 0 .
Contoh
x = 549
549 = 483 XOR (483 * 2) (as binary: 1000100101 = 111100011 XOR 1111000110)
483 = 161 XOR (161 * 2) (as binary: 111100011 = 10100001 XOR 101000010)
Yang berarti bahwa g 2 (161) = 549 . Kita tidak bisa melangkah lebih jauh, karena tidak ada n sedemikian sehingga g (n) = 161 . Jadi, output yang diharapkan untuk x = 549 adalah y = 161 .
Aturan
- Anda tidak seharusnya mendukung entri yang tidak valid. Sepasang (y, k) dijamin ada untuk nilai input x .
- Ini kode-golf , jadi jawaban tersingkat dalam byte menang!
Uji kasus
3 --> 1
5 --> 1
6 --> 2
9 --> 7
10 --> 2
23 --> 13
85 --> 1
549 --> 161
960 --> 64
1023 --> 341
1155 --> 213
1542 --> 2
9999 --> 2819
57308 --> 19124
57311 --> 223
983055 --> 1
a(n) = g(n)
Jawaban:
Java 8,
68575352 byte-5 byte terima kasih kepada @ OlivierGrégoire .
Cobalah online.
Penjelasan:
sumber
n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}
(52 byte). Maaf ^^ 'for(int i=0;n>i-=i+i^i^n?-1:n=i;);
?i+i^i^n?
bukan boolean, jadi tidak akan dikompilasi. Selain itu,n>i-=...
akan membutuhkan tanda kurung (n>(i-=...)
), dann=i
tidak diperbolehkan dalam klausa lain dari ternary-if, hanya dalam if-klausa (yang terakhir ini saya tidak tahu mengapa, tapi itulah yang ada di Jawa sayangnya ).n=i
tidak diizinkan dalam klausa lain dari ternary-if". Karena Jawa akan menguraikannya sebagai(i-=(i*2^i)!=n?-1:n)=i
yang ilegal.Python 2 ,
5453 byteCobalah online!
sumber
JavaScript, 53 byte
G
adalahg^-1
, yang diseteli
ke0
jika berhasil, diaturi
ke1
jika gagal.sumber
f=n=>(g=n=>n<2?0/!n:n%2+2*g(n/2^n%2))(n)?f(g(n)):n
. Sayangnya pendekatan yang membosankan lebih pendek 12 byte.Pyth ,
13 1210 byteDisimpan 1 byte berkat @MrXcoder, dan 2 byte lainnya mengikuti saran mereka
Cobalah online
Penjelasan:
sumber
T
selama 12 byte.R ,
7365 byteCobalah online!
Terima kasih banyak, Giuseppe (-8) karena tweak Anda, sangat sederhana namun sangat efektif
sumber
f=
karena fungsi tersebut harus terikatf
agar berfungsi dengan benar. Yang sedang berkata, kerja bagus, dan ambil +1 dari saya!JavaScript,
3836 byteCobalah online - Mulai melempar kesalahan overflow di antara
9999
&57308
.sumber
Jelly ,
87 byteGunakan
⁺¿
untuk mengembalikan elemen non-nol terakhir (terima kasih Dennis untuk -1 byte)Cobalah online!
Brute force menang lagi :(
sumber
^Ḥ)i$⁺¿
menghemat satu byte.C (gcc) ,
57565551 byte!=
~-
.bytelima byte berkat Rogem ; memanfaatkan ekspresi terner dan kebiasaan gcc.Cobalah online!
sumber
X(O,R)
for(R=1;R;O=R?R:O)
menghemat satu byte.R=O;
pada akhirnya tampaknya tidak perlu, menghemat 4 byte lagi.Z80Golf , 22 byte
Jawaban Java dari Port @ KevinCruijssen
Contoh dengan input 9-Coba online!
Contoh dengan input 85-Coba online!
Majelis:
Contoh perakitan untuk memanggil fungsi dan mencetak hasilnya:
sumber
a
penghitung lingkaran alih-alihd
, maka Anda dapat menggantild d,0
instruksi denganxor a
dua kali, yang menghemat dua byte.Java (JDK 10) , 78 byte
Cobalah online!
sumber
JavaScript (Node.js),
484538 byte-7 byte terima kasih kepada @Neil membuat versi rekursif dari versi iteratif saya di bawah ini. Tidak berfungsi untuk kasus uji besar.
Cobalah online.
Versi berulang 45 byte yang berfungsi untuk semua kasus uji:
Port jawaban Java saya.
-3 byte terima kasih kepada @Arnauld .
Cobalah online.
sumber
i-=i*2^i^n?-1:n=i
(tetapi sayangnya tidak di Jawa).1
di JS. Terima kasih!f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n
Ruby , 39 byte
Cobalah online!
Seperti yang diharapkan untuk versi rekursif, mengeluh tentang "tingkat tumpukan terlalu dalam" pada kasus uji terakhir.
sumber
Jelly ,
119 byteCobalah online!
Tips: Gunakan fungsi rekursif bukan loop.
Sangat cepat, sayangnya kalah dari pendekatan brute force.
Perhatikan bahwa:
Jadi, kami berulang kali:
B
)^\
atauÄḂ
, mereka memiliki efek yang sama).?
) ekor (elemen terakhir) (Ṫ
) dari akumulasi XOR adalah nol (jumlah pop aneh)ṛ
).sumber
B^\⁸Ḅß$Ṫ?
Keempat (gforth) , 71 byte
Cobalah online!
Penjelasan
sumber
Perl 6 , 44 byte
Cobalah
Diperluas:
sumber
Prolog (SWI) , 44 byte
Cobalah online!
sumber
PHP, 49 byte
Berdasarkan jawaban Kevin Cruijssen.
Jalankan sebagai pipa dengan
-nr
atau coba online .sumber
F #, 92 byte
Cobalah online!
Secara rekursif memeriksa angka-angka dari 1 hingga
i-1
. Jika ada kecocokan, periksa yang lebih kecil untuk nomor itu. Jika tidak ada yang cocok, kembalikan nomor input.sumber
JavaScript (Node.js) , 40 byte
Cobalah online!
Terima kasih Shaggy untuk -1 byte.
Port jawaban Jelly- ku .
Akhirnya ada bahasa di mana pendekatan ini
lebih pendek( oops ). (Saya mencoba Python dan Java , tidak berhasil)Adakah yang bisa menjelaskan mengapa saya bisa menggunakan
/2
bukan>>1
?sumber
x/2
bekerja karena aritmatika underflow. Setiap nomor IEEE 754 pada akhirnya akan dievaluasi sebagai 0 bila dibagi 2 kali cukup. (Dan bagian desimal diabaikan begitu saja ketika XOR, jadi ini tidak mempengaruhi hasilnya.)false
pada iterasi terakhir secara implisit dilemparkan ke0
oleh operator XOR bitwise.false
yang terlibat . JS&&
berperilaku hampir identik dengan Python / Luaand
.K (ngn / k) ,
3226 byteCobalah online!
{
}
adalah fungsi dengan argumenx
/
menerapkannya sampai konvergensi$[
;
;
]
jika-maka-lain2\x
digit biner darix
(ini khusus untuk ngn / k)+\
jumlah parsial2!
mod 2a:
ditugaskan kepadaa
*|
last - reverse (|
) dan get first (*
)jika di atas adalah 1,
x
akan dikembalikanjika tidak:
-1_a
drop elemen terakhir daria
2/
mendekode binersumber
C, 62 byte
Berdasarkan Java Kevin Cruijssen:
int n(int j){for(int i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}
Untuk menguji:
Saat dijalankan, program pengujian menghasilkan:
C, 54 byte
Hanya bekerja dengan C89 atau K&R C:
n(j){for(i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}
sumber
int n(int j){for(int i=0;j>i-=i*2^i^j?-1:j=i;);return j;}
Apakah 57 byte ini berfungsi?Bahasa Wolfram (Mathematica) , 58 byte
Cobalah online!
Mulai dengan daftar yang hanya berisi input. Iteratif mengganti daftar dengan semua bilangan bulat yang sudah ada di dalamnya, atau memetakannya dengan operasi double-and-xor. Lalu
//.
katakan untuk melakukan ini sampai mencapai titik yang tetap. Jawabannya adalah elemen paling sedikit dari hasilnya.sumber