24
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ In the example, the output variable should be m and not n, correct me if I'm wrong \$\endgroup\$
    – matteo_c
    Jun 22, 2022 at 9:48
  • \$\begingroup\$ @MatteoC. Correct, thanks for noticing this. \$\endgroup\$
    – Fatalize
    Jun 22, 2022 at 9:50
  • \$\begingroup\$ This doesn't actually have anything to do with base 2, it seems. It's purely about patterns of digits in base 10 numbers. I've sometimes seen bad beginner code that created numbers whose decimal digits were the 1s and 0s a binary number they were interested in, but that's usually an error, and very inefficient on a binary computer. TL:DR, I think I'm offended on behalf of binary numbers to have that name applied to these numbers. I have no inherent objection to the problem, I just wish it didn't call it "binary" without any caveats or qualifications. \$\endgroup\$ Jun 24, 2022 at 5:40
  • \$\begingroup\$ (And/or I'm worried that it's encouraging wrong thinking about numbers and bases, although I assume most programmers know better. Dividing it by 2 doesn't right-shift the pattern of 1s and 0s, instead creating 5s, so this isn't binary.) Sorry for the rant, this has been bugging me since that showed up in HNQ and turned out to have nothing to do with binary, other than using the same character set if printed as decimal / binary. \$\endgroup\$ Jun 24, 2022 at 5:41
  • 1
    \$\begingroup\$ This is actually checking if a number is a sum of different powers of 10, that would be one way to describe it. Debatable if the [binary] tag even applies, although some golf answers might possibly get something out of base 2 string validation perhaps. \$\endgroup\$ Jun 24, 2022 at 7:51

25 Answers 25

14
\$\begingroup\$

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!

\$\endgroup\$
9
\$\begingroup\$

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!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I think all(<'2') works here \$\endgroup\$
    – xnor
    Jun 23, 2022 at 1:21
  • \$\begingroup\$ I tried Arnauld's trick but only got 49: f n=until(all(<'2').show.(n-))(\m->sum[1|m<1]-m)0. But maybe the lambda can be shorter. \$\endgroup\$
    – xnor
    Jun 25, 2022 at 8:37
8
\$\begingroup\$

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.

\$\endgroup\$
0
6
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think a couple golfs can bring the first solution to 22 bytes: {(|/49<$x-){-x-x<1}/0} \$\endgroup\$
    – coltim
    Jun 30, 2022 at 21:49
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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\$

\$\endgroup\$
6
  • \$\begingroup\$ There's no return statement in the f function, isn't that undefined behavior? \$\endgroup\$ Jun 23, 2022 at 23:30
  • 1
    \$\begingroup\$ @IvanNeeson This is code golf so there can be a lot of UB. gcc will return the last assignment, so in this code n=m is a golf for return m. That's why the complier is stated in the post. \$\endgroup\$
    – Noodle9
    Jun 23, 2022 at 23:42
  • \$\begingroup\$ I see, good to know! \$\endgroup\$ Jun 24, 2022 at 0:43
  • \$\begingroup\$ You can remove r=m=0 if p;r;m are already 0 \$\endgroup\$
    – TKirishima
    Jul 6, 2022 at 21:40
  • \$\begingroup\$ @TKirishima Nope, the function has to be re-callable. \$\endgroup\$
    – Noodle9
    Jul 6, 2022 at 21:43
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ You have m<0?-m:-m at the end. Can be reduced to just -m. Typo, maybe? Should it be m<0?-m:m? \$\endgroup\$ Jun 23, 2022 at 20:29
  • 2
    \$\begingroup\$ The second '-' is actually a tilde '~' for bitwise NOT. \$\endgroup\$ Jun 23, 2022 at 23:27
  • \$\begingroup\$ looks more closely at phone... Oh, yeah! So it is. \$\endgroup\$ Jun 26, 2022 at 6:43
  • 1
    \$\begingroup\$ Can you use $"{n-m}".Max()<50? \$\endgroup\$
    – Neil
    Jun 26, 2022 at 7:46
  • \$\begingroup\$ You can indeed. Updated! \$\endgroup\$ Jun 26, 2022 at 23:16
3
\$\begingroup\$

Brachylog, 8 bytes

;.≜-ẹ~ḃ∧

Try it online!

Something less blunt seems possible.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think my test code was the same. \$\endgroup\$
    – Fatalize
    Jun 22, 2022 at 12:13
3
\$\begingroup\$

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
\$\endgroup\$
4
  • 2
    \$\begingroup\$ ݱ doesn't include 0, so all test cases that should result in 0 currently fail (e.g. \$n=1\$). Luckily Husk seems to have the sequence İZ including leading 0 as well by the looks of it. \$\endgroup\$ Jun 22, 2022 at 9:54
  • \$\begingroup\$ @KevinCruijssen - Thanks a lot - I hadn't spotted that. \$\endgroup\$ Jun 22, 2022 at 10:05
  • \$\begingroup\$ Np. :) (Your explanation "the infinite sequence of positive & negative integers 1,-1,2,-2,3,..." is still lacking the 0 -> "the infinite sequence of integers 0,1,-1,2,-2,3,...") \$\endgroup\$ Jun 22, 2022 at 12:36
  • \$\begingroup\$ @KevinCruijssen - Thanks again: fixed. \$\endgroup\$ Jun 22, 2022 at 14:33
3
\$\begingroup\$

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
    
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Isn't it shorter to just use \$length+1\$ instead of \$length\$ for the cartesian product of all 0/1 bits, instead of manually adding the \$10^{length}\$ item at the end? \$\endgroup\$ Jun 22, 2022 at 14:40
  • \$\begingroup\$ Nice catch, Kevin. I'll update explanation later. \$\endgroup\$
    – Jonah
    Jun 22, 2022 at 14:57
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ (n+k).to_s can be "#{n+k}", and f.call(n,k<0?-k:~k) can be f[n,k<0?-k:~k] \$\endgroup\$
    – naffetS
    Sep 1, 2022 at 22:16
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 84 bytes

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

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

BQN, 29 bytes

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

Try it here!

Port of Arnauld's answer.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Since you have to use a ternary operator, it's shorter to generate 0,-1,1,-2,2,... with r=r<0?-r:~r. \$\endgroup\$
    – Arnauld
    Jun 22, 2022 at 10:59
  • \$\begingroup\$ @Arnauld Ah, of course. Thanks! :) \$\endgroup\$ Jun 22, 2022 at 12:35
2
\$\begingroup\$

Pip, 41 bytes

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

Attempt This Online!

Argh.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 9 bytes

rNBḌ⁸_AÐṂ

Try it online!

Absolutely awful...

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 22 bytes

Nθ≔⁰ηW‹1⌈I⁻θη≔⁻‹η¹ηηIη

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

Nθ

Input n.

≔⁰η

Start testing with m=0.

W‹1⌈I⁻θη

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

≔⁻‹η¹ηη

Get the next value of m to test.

Iη

Output the found value of m.

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

Nθ≔IE⊕X²Lθ⍘ι²υ≔⁻θ⁺υ±υυI§υ⌕↔υ⌊↔υ

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

Nθ

Input n.

≔IE⊕X²Lθ⍘ι²υ

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.

I§υ⌕↔υ⌊↔υ

Output the value with the lowest absolute value.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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