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 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 at 17:10
  • 1
    This would be a nice fastest-code question as well (without the input size restriction) – qwr Aug 9 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 at 19:27

15 Answers 15

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 at 22:24
  • @Piccolo Can't believe I missed that, thanks! – Doorknob Aug 9 at 22:34

Jelly, 13 bytes

²,BL€EðƇ²^B§Ṃ

Try it online! or 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

²,BL€EðƇ²^B§Ṃ – Full program / Monadic link. Call the argument N.
      ðƇ      – Filter-keep [1 ... N] with the following dyadic chain:
²,BL€E        – The square of the current item has the same bit length as N.
²             – Square.
 ,            – Pair with N.
  B           – Convert both to binary.
   L€         – 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 at 23:09
  • @Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P – BWO Aug 8 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
  • 1
    Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though – Mr. Xcoder Aug 9 at 18:31
  • 1
    @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 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 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 at 21:20

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.

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 at 15:31
  • 1
    @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 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

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

NθI⌊EΦEθ↨×ιι²⁼LιL↨θ²ΣE↨責⁼λ§ιμ

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

Nθ                              Input N
       θ                        N
      E                         Map over implicit range
          ιι                    Current value (twice)
         ×                      Multiply
        ↨   ²                   Convert to base 2
     Φ                          Filter over result
               ι                Current value
                  θ             N
                 ↨ ²            Convert to base 2
              L L               Length
             ⁼                  Equals
    E                           Map over result
                       θ        N
                      ↨ ²       Convert to base 2
                     E          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
  I                             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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.