Biorąc pod uwagę liczbę całkowitą , musisz znaleźć minimalną liczbę bitów, którą należy odwrócić w aby przekształcić ją w liczbę kwadratową . Dozwolone jest tylko odwracanie bitów poniżej najbardziej znaczącego .$N>3$$N$

Przykłady

• $N=4$ już jest liczbą kwadratową ( ), więc oczekiwany wynik to .$2^2$$0$
• $N=24$ można zamienić na liczbę kwadratową, odwracając 1 bit: ( ), więc oczekiwany wynik to . 25 = 5 2$11000 \rightarrow 1100\color{red}1$$25=5^2$$1$
• 23 20 18 30 10110 → 10 0 0 0 16 = 4 2$N=22$ nie można zamienić na liczbę kwadratową poprzez odwrócenie pojedynczego bitu (możliwe wyniki to , , i ), ale można tego dokonać poprzez odwrócenie 2 bitów: ( ), więc oczekiwany wynik to .$23$$20$$18$$30$$10110 \rightarrow 10\color{red}0\color{red}00$$16=4^2$$2$

Zasady

• W porządku, jeśli Twój kod jest zbyt wolny lub generuje błąd dla większych przypadków testowych, ale powinien obsługiwać co najmniej w mniej niż 1 minutę.$3 < N < 10000$
• To jest golf golfowy !

Przypadki testowe

    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")

Lub w przyjaznym formacie kopiuj / wklej:

[4,22,24,30,94,831,832,1055,6495,9999,40063,247614,1049310,7361278,100048606]

Rubinowy, 74 bajty

->n{(1..n).map{|x|a=(n^x*x).to_s 2;a.size>Math.log2(n)?n:a.count(?1)}.min}

Wypróbuj online!

To po prostu generuje sekwencję (co jest znacznie więcej niż wystarczające), XORs za pomocą , a następnie przyjmuje liczbę 1s w postaci binarnej reprezentacja, jeśli liczba bitów jest mniejsza lub równa , lub innym przypadku. Następnie zajmuje minimalną liczbę przerzuconych bitów. Zwrócenie zamiast liczby przerzuconych bitów, gdy najwyższy przerzucony bit jest większy niż uniemożliwia tych przypadków jako minimum, ponieważ zawsze będzie większe niż liczba bitów, które ma. n log 2 nnn log 2 n$\left[1^2, 2^2, \ldots, n^2\right]$$n$$\log_2n$$n$$n$$\log_2n$$n$

Dzięki Piccolo za uratowanie bajtu.

Galaretka , 12 bajtów

²,BẈEðƇ²^B§Ṃ

Wypróbuj online!

Sprawdź pakiet testowy!

Link monadyczny. Powinien być golfowy. Ale jestem zbyt głupi, aby wymyślić sposób, aby się go pozbyć ³. To moja pierwsza odpowiedź, w której z powodzeniem używam filtrowania / mapowania / zapętlania ogólnie wraz z łańcuchem dynamicznym \ o /

Wyjaśnienie

², BẈEðƇ² ^ B§Ṃ - Pełny program / Łącze monadyczne. Wywołaj argument N.
     ðƇ - Zachowaj filtr [1 ... N] o następującym łańcuchu dyadycznym:
², BẈE - Kwadrat bieżącego elementu ma tę samą długość bitów co N.
² - kwadrat.
 , - Połącz z N.
  B - Konwertuj oba na binarne.
   Ẉ - Odzyskaj ich długości.
    E - I sprawdź, czy się równa.
       ² ^ - Po przefiltrowaniu wyrównaj wyniki i wyrównaj je za pomocą N.
         B - Binarna reprezentacja każdego.
          § - Suma każdego. Liczy liczbę 1 w postaci binarnej.
           Ṃ - minimum.

Łuska , 20 bajtów

▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

Wypróbuj online!

Wyjaśnienie

▼mΣf(¬→)S↑(M(¤ż≠↔ḋ)İ□ḋ) -- example input n=4
        S↑(           ) -- take n from n applied to (..)
                     ḋ  -- | convert to binary: [1,0,0]
                   İ□   -- | squares: [1,4,9,16,...]
           M(     )     -- | map with argument ([1,0,0]; example with 1)
                 ḋ      -- | | convert to binary: [1]
             ¤  ↔       -- | | reverse both arguments of: [1] [0,0,1]
              ż≠        -- | | | zip with inequality (absolute difference) keeping longer elements: [1,0,1]
                        -- | : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1],[1,0,1,1,1],....
                        -- : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1]]
    f(  )               -- filter elements where
       →                -- | last element
      ¬                 -- | is zero
                        -- : [[0,0,0]]
 mΣ                     -- sum each: [0]
▼                       -- minimum: 0

Perl 6 , 65 bajtów

{min map {+$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/\./},^2**.msb}

Wypróbuj online!

Czuję się trochę brudny, jeśli chodzi o testowanie idealnego kwadratu, szukając kropki w reprezentacji ciągu pierwiastka kwadratowego z liczby, ale ... cokolwiek, by zgolić bajty.

05AB1E , 20 15 bajtów

Lnʒ‚b€gË}^b€SOß

-5 bajtów dzięki @ Mr.Xcoder używający portu swojej odpowiedzi Jelly .

Wypróbuj online lub sprawdź wszystkie przypadki testowe (największe trzy przypadki testowe są usuwane, ponieważ przekroczą limit czasu po 60 sekundach; nadal zajmuje około 35-45 sekund w przypadku innych przypadków testowych).

Wyjaśnienie:

L            # Create a list in the range [1, input]
             #  i.e. 22 → [0,1,2,...,20,21,22]
 n           # Take the square of each
             #  i.e. [0,1,2,...,20,21,22] → [0,1,4,...,400,441,484]
  ʒ     }    # Filter this list by:
   ,         #  Pair the current value with the input
             #   i.e. 0 and 22 → [0,22]
             #   i.e. 25 and 22 → [25,22]
    b        #  Convert both to binary strings
             #   i.e. [0,22] → ['0','10110']
             #   i.e. [25,22] →  ['10000','11001']
     €g      #  Take the length of both
             #   i.e. ['0','10110'] → [1,5]
             #   ['10000','11001'] → [5,5]
       Ë     #  Check if both are equal
             #   i.e. [1,5] → 0 (falsey)
             #   i.e. [5,5] → 1 (truthy)
^            # After we've filtered, Bitwise-XOR each with the input
             #  i.e. [16,25] and 22 → [6,15]
 b           # Convert each to a binary string again
             #  i.e. [6,15] → ['110','1111']
  €S         # Change the binary strings to a list of digits
             #  i.e. ['110','1111'] → [['1','1','0'],['1','1','1','1']]
    O        # Take the sum of each
             #  i.e. [['1','1','0'],['1','1','1','1']] → [2,4]
ß            # And then take the lowest value in the list
             #  i.e. [2,4] → 2

Java (JDK 10) , 110 bajtów

n->{int i=1,s=1,b,m=99,h=n.highestOneBit(n);for(;s<h*2;s=++i*i)m=(s^n)<h&&(b=n.bitCount(s^n))<m?b:m;return m;}

Wypróbuj online!

Gaia , 18 bajtów

Bliski port mojej galaretki .

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

Wypróbuj online!

Awaria

s¦⟪, b¦l¦y⟫⁇ ⟪^ bΣ⟫¦⌋ - Pełny program. Nazwijmy wejście N.
s¦ - Kwadrat każdej liczby całkowitej w zakresie [1 ... N].
  ⟪⟫⁇ - Wybierz te, które spełniają określony warunek po przejściu
                     blokada dyadyczna. Użycie bloku dynamicznego pozwala zaoszczędzić jeden bajt, ponieważ
                     input, N, jest domyślnie używane jako kolejny argument.
   , - Sparuj bieżący element i literę N na liście.
    b¦ - Konwertuj je na binarne.
      l¦ - Zdobądź ich długości.
        y - Następnie sprawdź, czy są równe.
           ⟪⟫¦ - Przeprowadź wszystkie prawidłowe liczby całkowite przez blokadę.
            ^ - XOR każdy z N.
             bΣ - Konwertuj na binarny i sumuj (policz 1 w binarny)
                 ⌋ - minimum.

Brachylog , 56 41 bajtów

Nie pobije żadnych rekordów długości, ale i tak pomyślałem, że to opublikuję

⟨⟨{⟦^₂ᵐḃᵐ}{h∋Q.l~t?∧}ᶠ{ḃl}⟩zḃᶠ⟩{z{∋≠}ᶜ}ᵐ⌋

Wypróbuj online!

Zestaw x86-64, 37 bajtów

Kod bajtowy:

53 89 fb 89 f9 0f bd f7 89 c8 f7 e0 70 12 0f bd
d0 39 f2 75 0b 31 f8 f3 0f b8 c0 39 d8 0f 42 d8
e2 e6 93 5b c3

Cóż, to oblicza nawet najwyższy przykład w mniej niż sekundę.

Sercem algorytmu jest xor / popcount jak zwykle.

    push %rbx
    /* we use ebx as our global accumulator, to see what the lowest bit
     * difference is */
    /* it needs to be initialized to something big enough, fortunately the
     * answer will always be less than the initial argument */
    mov %edi,%ebx
    mov %edi,%ecx
    bsr %edi,%esi
.L1:
    mov %ecx,%eax
    mul %eax
    jo cont     /* this square doesn't even fit into eax */
    bsr %eax,%edx
    cmp %esi,%edx
    jnz cont    /* can't invert bits higher than esi */
    xor %edi,%eax
    popcnt %eax,%eax
    cmp %ebx,%eax   /* if eax < ebx */
    cmovb %eax,%ebx
cont:
    loop .L1
    xchg %ebx,%eax
    pop %rbx
    retq

Wolfram Language (Mathematica) , 67 bajtów

Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&

Wypróbuj online!

$\{1, 2, \ldots, n\}$BitLengthPickBitXorMinDigitCount1

Węgiel drzewny , 31 bajtów

ＮθＩ⌊ＥΦＥθ↨×ιι²⁼ＬιＬ↨θ²ΣＥ↨責⁼λ§ιμ

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

Ｎθ                              Input N
       θ                        N
      Ｅ                         Map over implicit range
          ιι                    Current value (twice)
         ×                      Multiply
        ↨   ²                   Convert to base 2
     Φ                          Filter over result
               ι                Current value
                  θ             N
                 ↨ ²            Convert to base 2
              Ｌ Ｌ               Length
             ⁼                  Equals
    Ｅ                           Map over result
                       θ        N
                      ↨ ²       Convert to base 2
                     Ｅ          Map over digits
                           λ    Current base 2 digit of N
                             ι  Current base 2 value
                              μ Inner index
                            §   Get digit of value
                          ⁼     Equals
                         ¬      Not (i.e. XOR)
                    Σ           Take the sum
   ⌊                            Take the minimum
  Ｉ                             Cast to string
                                Implicitly print

Galaretka , 20 bajtów

BL’Ø.ṗŻ€©Ḅ^⁸Ʋa§ɼ¹ƇṂ

Wypróbuj online!

Python 2 , 82 bajty

lambda n:min(bin(i*i^n).count('1')for i in range(n)if len(bin(i*i^n))<len(bin(n)))

Wypróbuj online!

Japt -g , 20 bajtów

Można to zagrać w golfa.

op f_¤Ê¥¢lî^U ¤¬xÃn

Wypróbuj online!

C (gcc) ,  93  91 bajtów

g(n){n=n?n%2+g(n/2):0;}m;i;d;f(n){m=99;for(i=0;++i*i<2*n;m=g(d=i*i^n)<m&d<n/2?g(d):m);n=m;}

Wypróbuj online!

Edycja: Wydaje mi się, że moje oryginalne rozwiązanie ( Wypróbuj online! ) Jest nieprawidłowe, ponieważ jedna ze zmiennych m, globalna w celu zaoszczędzenia kilku bajtów przez nieokreślenie typu, została zainicjowana poza f(n)i dlatego musiała zostać ponownie zainicjowana między wywołaniami

Kod nieposortowany i skomentowany:

g(n){n=n?n%2+g(n/2):0;} // returns the number of bits equal to 1 in n
m; //miminum hamming distance between n and a square
i; //counter to browse squares
d; //bitwise difference between n and a square
f(n){m=99; //initialize m to 99 > size of int (in bits)
    for(
        i=0;
        ++i*i<2*n; //get the next square number, stop if it's greater than 2*n
        g(d=i*i^n)<m&&d<n/2&&(m=g(d)) //calculate d and hamming distance
//      ^~~~~~~~~~~^ if the hamming distance is less than the minimum
//                    ^~~~^ and the most significant bit of n did not change (the most significant bit contains at least half the value)
//                           ^~~~~~~^ then update m
       );
    n=m;} // output m

Edycje:

• Zaoszczędzono 2 bajty dzięki pułapce cat