# 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? – Magic Octopus Urn Aug 9 '18 at 17:04
• @MagicOctopusUrn Thanks, I've updated the rules to make it more clear that supporting $N\ge 10000$ is optional. – Arnauld Aug 9 '18 at 17:10
• This would be a nice fastest-code question as well (without the input size restriction) – qwr Aug 9 '18 at 19:20
• @qwr Yes, probably. Or if you want to go hardcore: given $k$, find the smallest $N$ such that $f(N) = k$. – Arnauld Aug 9 '18 at 19:27

## 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);... – Piccolo Aug 9 '18 at 22:24
• @Piccolo Can't believe I missed that, thanks! – Doorknob Aug 9 '18 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. – Mr. Xcoder Aug 8 '18 at 23:09
• @Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P – ბიმო Aug 8 '18 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, 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

• Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though – Mr. Xcoder Aug 9 '18 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. – Kevin Cruijssen Aug 9 '18 at 19:12
• I guess I'm not good at writing test suites in 05AB1E ¯\_(ツ)_/¯, it's nice that you have fixed it :) – Mr. Xcoder Aug 9 '18 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 && – kirbyquerby Aug 9 '18 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.


# 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 – Kroppeb Aug 9 '18 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 – Kroppeb Aug 9 '18 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 – ceilingcat Aug 31 '18 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. – ObsequiousNewt Sep 2 '18 at 0:05

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

# 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 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;g(d=i*i^n)<m&&d<n/2&&(m=g(d)));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