How far from binary?

Question

Given a decimal integer n as input, output the smallest (in terms of absolute value) decimal integer m such that the absolute value of n-m is a binary integer (composed only of 1s and 0s).

n and m can be any integer, positive or negative.

Example

Let n = 702. The closest binary integer is 1000 = |702 - (-298)|, so m = -298.

Let n = -82. The closest binary integer in absolute value is 100 = |-82 - 18|, so m = 18.

Test Cases

Input n                Output m
0                      0
1                      0
4                      3
-4                     -3
6                      -4
15                     4
55                     44
56                     -44
-82                    18
702                    -298
-1000                  0

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

JavaScript (ES6), 43 bytes

Starting with \$k=0\$ and using the expression (k < 1) - k to update \$k\$ after each iteration, we recursively generate \$k=0,1,-1,2,-2,3,-3,\dots\$ (A001057) until the regular expression /[2-9]/ applied to \$n-k\$ doesn't match anything.

f=(n,k=0)=>/[2-9]/.test(n-k)?f(n,(k<1)-k):k

Try it online!

Answer 2

Haskell, 48 bytes

f n=[m|k<-[0..],m<-[k,-k],all(<'2')$show$n-m]!!0

Try it online!

xnor saved 7 bytes, thanks!

Answer 3

Python 2, 49 bytes

f=lambda n,m=0:f(n,(m<1)-m)if"1"<max(`n-m`)else m

Attempt This Online!

Port of Arnauld's answer, thanks to Kevin Cruijssen.

"1"<max(`n-m`) checks if any digits of n-m are more than 1, i.e. n-m is not a binary number.

Python 2, 68 bytes

lambda n:min((m for m in range(-n*n,n*n+1)if"2">max(`n-m`)),key=abs)

Attempt This Online!

The requirement to handle negative numbers is annoying.

Pretty naïve brute-force type method.

Answer 4

05AB1E, 6 bytes

LbI.x-

Try it online or verify all test cases or see this step-by-step output.

Explanation:

L       # Push a list in the range [1, (implicit) input-integer]
 b      # Convert each to a binary-string
  I     # Push the input-integer again
   .x   # Pop both, and keep the binary-string that's closest to the input
     -  # Subtract it from the (implicit) input-integer
        # (after which the result is output implicitly)

Answer 5

K (ngn/k), 22 bytes

{(|/49<$x-){-x-x<1}/0}

Try it online!

-3 bytes thanks to @coltim!

Port of Arnauld's answer.

My first-ever K submission! Been having a lot of fun learning all these APL-esque languages.

---

K (ngn/k), 34 bytes

{*a@<a|-a:x-,/-:\.'""/'$+!2,2|^$x}

Try it online!

Wanted to find another approach, but it ended up becoming @Jonah's approach.

Explanation

Input is x.

• +!2,2|^$x binary sequences of (length of x)+1
• .'""/'$ join each binary sequence and convert to decimal
• ,/-:\ append negatives
• x- subtract x from each
• *a@<a|-a: absolute minimum

Answer 6

Whitespace, 193 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][N
S S N
_Create_Label_OUTER_LOOP][S N
S _Duplicate_m][S S S N
_Push_0][T  T   T   _Retrieve_input][S N
T   _Swap_top_two][T    S S T   _Subtract_:_input-m][S N
S _Duplicate_input-m][N
T   T   S N
_If_neg_jump_to_Label_ABS][N
S S T   N
_Create_Label_INNER_LOOP][S N
S _Duplicate_abs(input-m)][N
T   S S S N
_If_0_jump_to_Label_PRINT_RESULT][S N
S _Duplicate][S S S T   S T S N
_Push_10][T S T T   _Modulo_:_abs(input-m)%10][S S S T  S N
_Push_2][T  S S T   _Subtract_:_abs(input-m)%10-2][N
T   T   S T N
_If_neg_jump_to_Label_CONTINUE_INNER][S N
N
_Discard_top][S S T T   N
_Push_-1][T S S N
_Multiply_:_-m][S N
S _Duplicate][N
T   T   T   S N
_If_neg_jump_to_Label_NON_NEG][S N
S _Duplicate][N
T   S T S N
_If_0_jump_to_Label_NON_NEG][N
S N
N
_Jump_to_Label_OUTER_LOOP][N
S S S N
_Create_Label_ABS][S S T    T   N
_Push_-1][T S S N
_Multiply_:_abs(input-m)][N
S N
T   N
_Jump_to_Label_INNER_LOOP][N
S S S T N
_Create_Label_CONTINUE_INNER][S S S T   S T S N
_Push_10][T S T S _Integer_divide_:_abs(input-m)//10][N
S N
T   N
_Jump_to_Label_INNER_LOOP][N
S S T   S N
_Create_Label_NON_NEG][S S S T  N
_Push_1][T  S S T   _Subtract_:_-m-1][N
S N
N
_Jump_to_Label_OUTER_LOOP][N
S S S S N
_Create_Label_PRINT_RESULT][S N
N
_Discard_top][T N
S T _Print_to_STDOUT_as_integer]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Just like my Java answer, this is an iterative port of @Arnauld's JavaScript answer.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer m = 0
Read STDIN as integer
Start OUTER_LOOP:
  Integer t = abs(input - m)
              (abs is necessary because of the modulo-10 on negative values)
  Start INNER_LOOP:
    If t ==0:
      Print m as integer to STDOUT
      (implicitly stop the program with an error: no exit defined)
    Integer p = t modulo-10
    If p-2 <0 (thus either 0 or 1):
      t = t integer-divided by 10
      Continue INNER_LOOP
    m = -m
    If m <=0:
      m = m - 1
      Continue OUTER_LOOP
    Continue OUTER_LOOP

Answer 7

C (gcc), 78 bytes

p;r;m;f(n){for(r=m=0;r=!r;m=r?m:(m<1)-m)for(p=abs(n-m);p;p/=10)r&=p%10<2;n=m;}

Try it online!

Uses Arnauld's idea from his Javascipt answer to generate \$m=0,1,-1,2,-2\dots\$

Answer 8

Factor + math.unicode, 73 66 62 bytes

[ 0 [ 2dup - >dec "-01" ⊂ ] [ dup 1 < 1 0 ? swap - ] until ]

A port of @Arnauld's JavaScript answer. Needs modern Factor for >dec, so no TIO/ATO link. Here's a version that works on TIO for 2 more bytes, though:

Try it online!

Answer 9

Scala, 54 bytes

n=>(-n*n to n*n)filter(m=>(n-m+"").max<50)minBy(_.abs)

A bit late to the party. All tricks I came up with were already in use by somebody else. However, the -n*n to n*n trick by @pxeger was new to me, thanks!

Try it online!

Answer 10

C# (Visual C# Interactive Compiler), 57 bytes

-4 thanks to Neil

int@B(int@n,int@m=0)=>$"{n-m}".Max()<50?m:B(n,m<0?-m:~m);

Try it online!

Kinda abuses the fact that the Visual C# Interactive Compiler mode seems to import System.Linq by default.

A version that doesn't use Linqin 87 bytes

int@B(int@n,int@m=0)=>$"{n-m}".IndexOfAny("23456789".ToCharArray())<0?m:B(n,m<0?-m:~m);

Try it online!

Answer 11

Brachylog, 8 bytes

;.≜-ẹ~ḃ∧

Try it online!

Something less blunt seems possible.

Answer 12

Husk, 9 bytes

Edit: bug fixed thanks to Kevin Cruijssen (same bytes)

ḟȯΛεd≠⁰İZ

Try it online!

ḟ          # find the first element of
       İZ  # the infinite sequence of positive & negative integers 0,1,-1,2,-2,3,...
 ȯ         # that satisfies (composition of 3 functions):
  Λ        # all of the
    d      # decimal digits of the
     ≠⁰    # absolute difference to the input
   ε       # are at most 1

Answer 13

J, ^{45 41 40} 38 bytes

-0{[(]/:|@-/)[:(,-)10#.[:#:@i.2^1+#@":

Try it online!

-4 thanks to Kevin Cruijssen

This is much longer than a port of Arnauld's answer would have been, but I figured a different conceptual approach might be interesting, and in another language the approach might even be shorter:

Consider 702:

• It's length is 3.

• Generate integers 0... 2^3, in binary:

  0 0 0
  0 0 1
  0 1 0
  0 1 1
  1 0 0
  1 0 1
  1 1 0
  1 1 1
  

• Convert them to decimal

  0 1 10 11 100 101 110 111
  

• Add their negative values too:

  0 1 10 11 100 101 110 111 0 _1 _10 _11 _100 _101 _110 _111
  

• Also add 10^<length of input> = 1000

  0 1 10 11 100 101 110 111 0 _1 _10 _11 _100 _101 _110 _111 1000
  

• Find which of these numbers has the smallest absolute different with the input:

  1000
  

• Original input minus that.

  _298
  

Answer 14

Ruby, 53 bytes

f=->n,k=0{(n+k).to_s=~/[2-9]/?f.call(n,k<0?-k:~k):-k}

Try it online!

Port of Arnauld's answer.

Answer 15

Vyxal, 15 bytes

0λ?εf1>a;₍><⁽ȧ∵

Try it Online!

How?

0λ?εf1>a;₍><⁽ȧ∵
         ₍      # Apply both of the following two commands and wrap the results in a list:
          >     #  Increment until lambda returns false...
           <    #  and decrement until lambda returns false.
 λ      ;       # With the following lambda:
  ?ε            #  Absolute difference with input
    f           #  List of digits
     1>a        #  Are there any that are greater than 1?
0               # ...starting from 0.
            ⁽ȧ∵ # Take the minimum of these two by the absolute value.

Another 15 byter: Nṡ:ȧbvṅ⌊$±*-⁽ȧ∵. In fact, :ȧbvṅ⌊$±* is all to create a binary string, but handling negative values.

Answer 16

Haskell, 84 bytes

f n=head$filter(all(`elem`"-10").show.(n-))$concat$zipWith(\a b->[a,b])[0,-1..][1..]

Attempt This Online!

Answer 17

BQN, 29 bytes

{'1'<⌈´•Fmt|𝕨-𝕩?𝕨𝕊<⟜1⊸-𝕩;𝕩}⟜0

Try it here!

Port of Arnauld's answer.

Answer 18

Java 8, 69 68 bytes

n->{int m=0;for(;!(n-m+"").matches("[01-]+");m=m<0?-m:~m);return m;}

Iterative port of @Arnauld's JavaScript answer, and an additional -1 thanks to @Arnauld as well.

Try it online.

Explanation:

n->{                      // Method with integer as both parameter & return-type
  int m=0;                //  Result-integer, starting at 0
  for(;!(n-m+"")          //  Loop as long as n-m converted to a String
        .matches("[01-]+")//  contains anything other than just 0s/1s/"-"s
      ;                   //    After every iteration:
     //m=m<0?-m:~m        //     (iterate to the next `m` in 0,1,-1,2,-2,3,...)
       m=                 //     Update the result to:
         m<0?             //      If the result is negative:
             -m           //       Change it to its positive form
               :          //      Else (it's 0 or positive):
                ~m)       //       Change it to -m-1 instead
  ;                       //  After the loop,
   return m;}             //  simply return the result

Answer 19

Pip, 41 bytes

Fh,2{W$|1<_M^aAD(h?iv){h?UiDv}}ABi<ABv?iv

Attempt This Online!

Argh.

Answer 20

Retina 0.8.2, 112 bytes

$
¶$`
(¶-?)(([01]*)0)?(5*[6-9].*)
$1${3}1$.4$*0
(¶[-01]*)([2-9].*)
$1$.2$*1
\d+
$*
(1*)¶-?\1
-
--

r`(1*)-*$
$.1

Try it online! Link includes test cases. Explanation:

$
¶$`

Duplicate the input.

(¶-?)(([01]*)0)?(5*[6-9].*)
$1${3}1$.4$*0

If the second copy has a digit between 6 and 9, optionally preceded by any number of 5s, either at the start of the number or after a 0, then round those 5-9s away from zero. For example, -1056 rounds to -1100.

(¶[-01]*)([2-9].*)
$1$.2$*1

Otherwise if it still has a digit of at least 2 then "round it towards zero" (fill with 1s). For example, 19 rounds to 11.

\d+
$*

Convert to unary.

(1*)¶-?\1
-

Subtract the two numbers.

--

If we subtracted a more negative number from another, the result is now positive. (This saves a byte over doing it in the decimal conversion.)

r`(1*)-*$
$.1

Convert to decimal, ignoring any trailing -s which result when the first number's absolute value is no less than the second.

Answer 21

Jelly, 9 bytes

rNBḌ⁸_AÐṂ

Try it online!

Absolutely awful...

Answer 22

Charcoal, 22 bytes

Ｎθ≔⁰ηＷ‹1⌈Ｉ⁻θη≔⁻‹η¹ηηＩη

Try it online! Link is to verbose version of code. Explanation: Port of @pxeger's Python port of @Arnauld's JavaScript answer.

Ｎθ

Input n.

≔⁰η

Start testing with m=0.

Ｗ‹1⌈Ｉ⁻θη

Repeat while n-m contains a digit greater than 1.

≔⁻‹η¹ηη

Get the next value of m to test.

Ｉη

Output the found value of m.

31 bytes for an efficient version that uses @Jonah's alternative approach:

Ｎθ≔ＩＥ⊕Ｘ²Ｌθ⍘ι²υ≔⁻θ⁺υ±υυＩ§υ⌕↔υ⌊↔υ

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

Ｎθ

Input n.

≔ＩＥ⊕Ｘ²Ｌθ⍘ι²υ

Generate all the base 2 values from 0 to the first value whose length in base 2 exceeds n's length, and interpret the base 2 values as base 10.

≔⁻θ⁺υ±υυ

Append the negations of those values, and then subtract all of them from n.

Ｉ§υ⌕↔υ⌊↔υ

Output the value with the lowest absolute value.

Answer 23

Pyth, 15 bytes

-QhaDQ.m-`bT+Uy

Try it online! or Try all test cases

-QhaDQ.m-`bT+Uy(QQ)
                    # Implicitly initialize Q as the input
             UyQ    # Range from 0 to 2*Q (half-inclusive)
            +   Q   # Append Q (necessary for the 0 case)
      .m            # Filter for elements `b` that are minimized by...
        -`b         #  ...the string representation of `b` minus...
           T        #  ... the characters in "10"
   aDQ              # Sort by absolute difference from Q
  h                 # Take the first element
-Q                  # Subtract that from Q

Answer 24

PARI/GP, 52 bytes

n->k=0;while(n-k&&vecmax(digits(n-k))>1,k=(k<1)-k);k

Attempt This Online!

A port of @Arnauld's JavaScript answer.

Answer 25

Perl 5 + -al060p, 36 bytes

$_="@F"-($\=($\<1)-$\)while/[2-9]/}{

Try it online!

Explanation

A translation of @Arnauld's JavaScript answer. $\ is initialised to 0 via the -l060 flag and $_ is set to the original number (stored in @F at index 0 via -a, interpolated as "@F") with $\ subtracted, and can then be matched via bare m// for digits 2-9.