# Toggle some bits and get a square

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 !

## 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]

• Almost half of the answers don't execute for 100048606 on TIO, is that a problem? Commented Aug 9, 2018 at 17:04
• @MagicOctopusUrn Thanks, I've updated the rules to make it more clear that supporting $N\ge 10000$ is optional. Commented Aug 9, 2018 at 17:10
• This would be a nice fastest-code question as well (without the input size restriction)
– qwr
Commented Aug 9, 2018 at 19:20
• Links to user accounts in the LINKS section are problematic, but it should work under CODE. Hope this is ok for you. I'm curious if someone from the OEIS community will try an extension. Commented Dec 16, 2022 at 15:21
• In the meantime, the sequence A358701 has actually received an additional term. Michael S. Branicky found $a(9)=743300286$, almost certainly using a Python program. You can also use this as a test if you want to determine the efficiency of the programs presented here. Commented Jan 12, 2023 at 8:17

## 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.

• You can save a byte by using (n^x*x).to_s 2;... instead of (n^x*x).to_s(2);... Commented Aug 9, 2018 at 22:24
• @Piccolo Can't believe I missed that, thanks! Commented Aug 9, 2018 at 22:34

# 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.


# 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

• ▼mΣfo¬←ṠMz≠ȯfo£İ□ḋπŀ2Lḋ saves 2 bytes. RIP you perfect square score. Commented Aug 8, 2018 at 23:09
• @Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P Commented Aug 8, 2018 at 23:12

# 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.

# 05AB1E, 2015 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)

• Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though Commented Aug 9, 2018 at 18:31
• @Mr.Xcoder Thanks! And my test suite almost always breaks after I golf something.. XD But it's fixed now as well. Commented Aug 9, 2018 at 19:12
• I guess I'm not good at writing test suites in 05AB1E ¯\_(ツ)_/¯, it's nice that you have fixed it :) Commented Aug 9, 2018 at 19:38

# 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!

• You can save 1 byte by using bitwise and & instead of logical and && Commented Aug 9, 2018 at 21:20

# Gaia, 18 bytes

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.


# 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.

# 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!

• Just realized zipping is a thing. I'll shorten it after i come back from diner Commented Aug 9, 2018 at 15:31
• @Arnauld Yeah, the main problem was that for each i in range(0,n+1) i recalculated the range, squared it and to binary. Putting this outside recuired a few more bytes but it's way faster now Commented Aug 9, 2018 at 20:36

# 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

• Suggest replacing at least one of your movs with an xchg Commented Aug 31, 2018 at 23:55
• As far as I can tell there's only one that would save a byte (mov %ecx,%eax) and I can't let %ecx die there. Commented Sep 2, 2018 at 0:05
• answer will always be less than the initial argument why, what env?---See the mov
– l4m2
Commented Dec 16, 2022 at 11:32

# 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.


# 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


# Jelly, 20 bytes

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


Try it online!

# 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!

# Japt-g, 20 bytes

This can be golfed down.

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


Try it online!

# 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
• Why d<n/2? I tried some case d>=n/2 but they end up different d
– l4m2
Commented Dec 16, 2022 at 12:19

# 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