Toggle some bits and get a square

Question

Given an integer \$N>3\$, you have to find the minimum number of bits that need to be inverted in \$N\$ to turn it into a square number. You are only allowed to invert bits below the most significant one.

Examples

• \$N=4\$ already is a square number (\$2^2\$), so the expected output is \$0\$.
• \$N=24\$ can be turned into a square number by inverting 1 bit: \$11000 \rightarrow 1100\color{red}1\$ (\$25=5^2\$), so the expected output is \$1\$.
• \$N=22\$ cannot be turned into a square number by inverting a single bit (the possible results being \$23\$, \$20\$, \$18\$ and \$30\$) but it can be done by inverting 2 bits: \$10110 \rightarrow 10\color{red}0\color{red}00\$ (\$16=4^2\$), so the expected output is \$2\$.

Rules

• It is fine if your code is too slow or throws an error for the bigger test-cases, but it should at least support \$3 < N < 10000\$ in less than 1 minute.
• This is code-golf!

Test cases

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

Or in copy/paste friendly format:

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

Answer 1

Ruby, 74 bytes

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

Try it online!

This simply generates the sequence \$\left[1^2, 2^2, \ldots, n^2\right]\$ (which is far more than enough), XORs it with \$n\$, and then takes either the number of 1s in its binary representation if the number of bits is less than or equal to \$\log_2n\$, or \$n\$ otherwise. It then takes the minimum number of bits flipped. Returning \$n\$ instead of the number of bits flipped when the highest bit flipped is greater than \$\log_2n\$ prevents these cases from being chosen as the minimum, as \$n\$ will always be greater than the number of bits it has.

Thanks to Piccolo for saving a byte.

Answer 2

Jelly, 12 bytes

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

Try it online!

Check out a test suite!

Monadic link. Should be golfable. But I am too dumb to think of a way to get rid of the ³s. It's my first answer in which I successfully use filtering / mapping / looping in general along with a dyadic chain \o/

Explanation

²,BẈEðƇ²^B§Ṃ – Full program / Monadic link. Call the argument N.
     ðƇ      – Filter-keep [1 ... N] with the following dyadic chain:
²,BẈE        – The square of the current item has the same bit length as N.
²            – Square.
 ,           – Pair with N.
  B          – Convert both to binary.
   Ẉ         – Retrieve their lengths.
    E        – And check whether they equate.
       ²^    – After filtering, square the results and XOR them with N.
         B   – Binary representation of each.
          §  – Sum of each. Counts the number of 1s in binary.
           Ṃ – Minimum.

Answer 3

Husk, 20 bytes

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

Try it online!

Explanation

▼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

Answer 4

Perl 6, 65 bytes

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

Try it online!

I feel a little dirty for testing for a perfect square by looking for a period in the string representation of the number's square root, but...anything to shave off bytes.

Answer 5

05AB1E, 20 15 bytes

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

-5 bytes thanks to @Mr.Xcoder using a port of his Jelly answer.

Try it online or verify all test cases (biggest three test cases are removed because they time out after 60 sec; still takes about 35-45 sec with the other test cases).

Explanation:

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

Answer 6

Java (JDK 10), 110 bytes

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;}

Try it online!

Answer 7

Gaia, 18 bytes

Near-port of my Jelly answer.

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

Try it online!

Breakdown

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋ – Full program. Let's call the input N.
s¦                 – Square each integer in the range [1 ... N].
  ⟪      ⟫⁇        – Select those that fulfil a certain condition, when ran through
                     a dyadic block. Using a dyadic block saves one byte because the
                     input, N, is implicitly used as another argument.
   ,               – Pair the current element and N in a list.
    b¦             – Convert them to binary.
      l¦           – Get their lengths.
        y          – Then check whether they are equal.
           ⟪   ⟫¦  – Run all the valid integers through a dyadic block.
            ^      – XOR each with N.
             bΣ    – Convert to binary and sum (count the 1s in binary)
                 ⌋ – Minimum.

Answer 8

Brachylog, 56 41 bytes

It's not gonna break any length records but thought i'd post it anyway

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

Try it online!

Answer 9

x86-64 assembly, 37 bytes

Bytecode:

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

Nicely, this computes even the highest example in less than a second.

Heart of the algorithm is xor/popcount as usual.

    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

Answer 10

Wolfram Language (Mathematica), 67 bytes

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

Try it online!

Takes \$\{1, 2, \ldots, n\}\$ and squares them. Then, the numbers with same BitLength as the input are Picked, and BitXored with the input. Next, the Minimum DigitCount of 1s in binary is returned.

Answer 11

Charcoal, 31 bytes

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

Try it online! Link is to verbose version of code. Explanation:

Ｎθ                              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

Answer 12

Jelly, 20 bytes

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

Try it online!

Answer 13

Python 2, 82 bytes

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

Try it online!

Answer 14

Japt -g, 20 bytes

This can be golfed down.

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

Try it online!

Answer 15

C (gcc),  93  91 bytes

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;}

Try it online!

---

Edit: I think my original solution (Try it online!) is not valid, because one of the variables, m, global to save a few bytes by not specifying type, was initialized outside of f(n) and therefore had to be reinitialized between calls

---

Ungolfed and commented code :

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

---

Edits:

• Saved 2 bytes thanks to ceilingcat