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 14 bytes

Lnʒ‚b€gË}^b1öß

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

Try it online or verify all test cases (the biggest four test cases are removed, because they'll timeout after 60 sec).

Explanation:

L          # Create a list in the range [1, (implicit) input-integer]
           #  i.e. input=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 (implicit) input-integer
           #   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 (implicit) input-integer
           #  i.e. [16,25] and 22 → [6,15]
 b         # Convert each to a binary string again
           #  i.e. [6,15] → ['110','1111']
  1ö       # Convert each to base-1, which effectively is a vectorized sum of their
           # digits, to get the amount of 1-bits in each binary string
           #  i.e. ['110','1111'] → [2,4]
ß          # Pop and leave the minimum of this list
           #  i.e. [2,4] → 2
           # (which is output implicitly as result)

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

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 9

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 10

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 11

PARI/GP 136 bytes

t(n)=b=#digits(n\2,2);for(j=0,b,v=concat(vector(b-j),vector(j,i,1));forperm(v,p,if(issquare(bitxor(n,fromdigits(Vec(p),2))),return(j))))

Test

T=[4, 22, 24, 30, 94, 831, 832, 1055, 6495, 9999, 40063, 247614, 1049310, 7361278, 100048606];
for (i=1, #T, print(T[i]," | "t(T[i])))
4 | 0
22 | 2
24 | 1
30 | 3
94 | 4
831 | 5
832 | 1
1055 | 4
6495 | 6
9999 | 4
40063 | 6
247614 | 7
1049310 | 7
7361278 | 8
100048606 | 8
> ##
***   last result computed in 736 ms.

Test with OEIS A358701(9):
t(743300286)
9
##
last result computed in 3,813 ms.

Answer 12

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 13

Jelly, 20 bytes

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

Try it online!

Answer 14

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 15

Japt -g, 20 bytes

This can be golfed down.

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

Try it online!

Answer 16

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

Answer 17

JavaScript (Node.js), 79 bytes

x=>g=(i=z=x)=>i?g(i-1,t=i*i^x,u=(N=i=>i&&i%2+N(i>>1))(t),z=z<u|t>x&i*i>x?z:u):z

Try it online!

If t and t^x are both larger than x then t is longer than x