You are playing a famous game called \$1\text{D Array BattleGround}\$. In the game, the player can be stationed in any position from \$0\$ to \$10^5\$.

You are a Paratrooper in the game and have the ability to do two types of operation \$-\$

  • Advance, which would multiply your position by \$2\$
  • Fall-back, which would decrease your current position by \$1\$

Each type of operation requires \$1\$ second.

You are stationed in \$N\$ and want to go to \$M\$ in the minimum time possible, (\$1≤ N, M ≤10^4\$).

Find out the minimum time you need to Get to \$M\$.

Note: After each operation, you must remain in the zone from \$0\$ to \$10^5\$.


Input : 4 6
Output: 2

Input : 10 1
Output: 9

Input : 1 3
Output: 3

Input : 2 10
Output: 5

Input : 666 6666
Output: 255

Input : 9999 10000
Output: 5000

This is a code-golf challenge so code with lowest bytes wins!

  • 1
    \$\begingroup\$ Ah, my bad. I read that as increase, but it clearly says multiply. Sorry about that. \$\endgroup\$
    – Adám
    Jun 17, 2020 at 17:44
  • 5
    \$\begingroup\$ No, I made it myself. \$\endgroup\$ Jun 17, 2020 at 20:39
  • 1
    \$\begingroup\$ It seems like there should be a number theory equivalent to this. \$\endgroup\$ Jun 18, 2020 at 2:05
  • 1
    \$\begingroup\$ Could you wrap a bold around the multiply? I read it as increase too! \$\endgroup\$
    – mkst
    Jun 18, 2020 at 10:34
  • 1
    \$\begingroup\$ @streetster Thank you for pointing it out :) \$\endgroup\$ Jun 18, 2020 at 13:39

14 Answers 14


JavaScript (ES6), 30 bytes

Takes input as (N)(M).


Try it online!


Instead of going from \$N\$ to \$M\$, we go from \$M\$ to \$N\$.

While \$M\$ is greater than \$N\$:

  • if \$M\$ is odd, increment it and divide it by \$2\$ (2 operations)
  • if \$M\$ is even, just divide it by \$2\$ (1 operation)

When \$M\$ is less than or equal to \$N\$, the remaining number of operations is \$N-M\$.

Example for \$N=666\$, \$M=6666\$:

  M   | transformation     | operations | total
 6666 | M / 2       = 3333 |      1     |   1
 3333 | (M + 1) / 2 = 1667 |      2     |   3
 1667 | (M + 1) / 2 = 834  |      2     |   5
 834  | M / 2       = 417  |      1     |   6
 417  | M + 249     = 666  |     249    |  255

With inverse operations in reverse order, this gives:

$$((((666-249)\times 2)\times 2-1)\times 2-1)\times 2=6666$$

The idea behind that is that it's always cheaper to process the greatest number of fall-back operations at the beginning of the process (i.e. when \$N\$ is still small) rather than exceeding \$M\$ by too large a margin with hasty advance operations and doing fall-backs afterwards.

  • 1
    \$\begingroup\$ Is there a proof that this procedure gives the minimum number of steps? \$\endgroup\$
    – Luis Mendo
    Jun 17, 2020 at 20:02
  • 9
    \$\begingroup\$ @LuisMendo Oh yes ... Yes, there is! ... hurried footsteps ... door slamming ... \$\endgroup\$
    – Arnauld
    Jun 17, 2020 at 20:18
  • 1
    \$\begingroup\$ This looks right, I think I have an argument why it always works. \$\endgroup\$
    – xnor
    Jun 17, 2020 at 20:29
  • 12
    \$\begingroup\$ When considering going from M to N like you're doing, the reversed operations are halving (only for evens) and incrementing. Once M is below N, the only thing to do is to increment it up to N, since making it smaller first would be silly. Before that, we never want to increment twice in a row, since later we'll halve, and increment-increment-halve can be shortened to with halve-increment. This leaves us with only sequences made of halve and increment-halve. These can only be applied to even and odd numbers respectively, and so can be chosen based on parity as in your procedure. \$\endgroup\$
    – xnor
    Jun 17, 2020 at 20:55
  • 1
    \$\begingroup\$ (And the limit of 10,000 never comes up because it's even, so you never increment above it.) \$\endgroup\$
    – xnor
    Jun 17, 2020 at 20:57

C (gcc), 53 34 bytes

Saved a whopping 19 bytes thanks to the man himself Arnauld!!!


Try it online!

A port of Arnauld's JavaScript answer.

  • 1
    \$\begingroup\$ A more direct port would work as well. :) \$\endgroup\$
    – Arnauld
    Jun 17, 2020 at 18:58
  • \$\begingroup\$ @Arnauld Wow! Was wondering if recursion would help and does it ever - thanks! :D \$\endgroup\$
    – Noodle9
    Jun 17, 2020 at 19:37
  • \$\begingroup\$ This doesn't return the answer, merely calculate it. Is it required for code gold answers to return output? \$\endgroup\$
    – Chipster
    Jun 21, 2020 at 23:05
  • \$\begingroup\$ @Chipster It most certainly does return the answer! Click on Try it online and see for yourself. \$\endgroup\$
    – Noodle9
    Jun 22, 2020 at 2:13
  • \$\begingroup\$ Hmm, I see it. Does C return things implicitly? \$\endgroup\$
    – Chipster
    Jun 22, 2020 at 2:19

APL (Dyalog Unicode), 24 bytes SBCS

Recursive dfn as per Arnauld's answer.


Try it online! We take Arnauld's approach but we use APL's nice builtins to make a single recursive call instead of having to choose the recursive call that we want to make (which would depend on the parity of M):

{⍵≤⍺:⍺-⍵⋄(2|⍵)+1+⍺∇⌈⍵÷2} ⍝ dfn taking N on the left and M on the right
{⍵≤⍺:                    } ⍝ if N is less than or equal to M
      ⍺-⍵                  ⍝ just return N - M
          ⋄                 ⍝ otherwise
                   ⍺∇⌈⍵÷2  ⍝ divide M by 2, round up and call this function recursively
                 1+         ⍝ to which we add 1 unconditionally
          (2|⍵)+            ⍝ and to which we add the parity of M, i.e. add one more iff M is odd.

Husk, 11 bytes


Try it online! Arguments are in reversed order (first target, then initial position).


Brute force turned out shorter than more efficient methods.

←V€⁰¡ṁ§eD←;  Inputs: M (stored in ⁰) and N (implicit).
          ;  Wrap in list: [N]
    ¡        Iterate, returning an infinite list:
     ṁ         Map and concatenate:
         ←       Decrement and
        D        double,
      §e         put the results in a two-element list.
 V           1-based index of first list that
  €⁰         Contains M.
←            Decrement.
  • \$\begingroup\$ This solution is producing tle for the last case where \$N=9999 \$ and \$ M= 10000.\$ Were you able to produce a result from that case? \$\endgroup\$ Jun 18, 2020 at 19:42
  • 1
    \$\begingroup\$ @JubayerAbdullahJoy TIO cuts execution time at 60 seconds. It should eventually finish if I run it locally. I can try that tomorrow. \$\endgroup\$
    – Zgarb
    Jun 18, 2020 at 19:53
  • 1
    \$\begingroup\$ @JubayerAbdullahJoy Well, the program quickly filled my computer's memory and I had to kill it. I maintain that it's correct in the sense that given enough time and memory, it will eventually output 5000, even though it's practically untestable. \$\endgroup\$
    – Zgarb
    Jun 19, 2020 at 16:19
  • \$\begingroup\$ oh, I am new to code-golf. What should we do if a solution can't be verified? Can it be accepted? :( \$\endgroup\$ Jun 19, 2020 at 16:44
  • 1
    \$\begingroup\$ There has been some discussion on our meta site (here and here) about untestable answers. The consensus seems to be that an explained solution that works on small inputs and seems scalable is acceptable, unless of course someone finds inputs on which it fails. OTOH, since Husk and JavaScript are like apples and oranges, consider not accepting any answer. \$\endgroup\$
    – Zgarb
    Jun 19, 2020 at 19:08

Jelly, 13 bytes

Took quite a while to find an approach which could be implemented in under 16 bytes.


A dyadic Link accepting M on the left and N on the right which yields the time you need to manoeuvre.

Try it online!


‘:Ḃȯ⁹>$Ɗ?Ƭ2i’ - Link: M, N
          2   - use two as the right argument (R) of:
         Ƭ    -   collect up, starting at M, while results are distinct:
        ?     -     if...
       Ɗ      -     ...condition: last three links as a monad - i.e. f(current_value):
  Ḃ           -       LSB (i.e. is current_value odd?)
      $       -       last two links as a monad:
     ⁹        -         chain's right argument, N
    >         -         greater than? (i.e. is current_value less than N?)
   ȯ          -       logical OR (i.e. is current_value either odd or less than N?)
‘             -     ...then: increment
 :            -     ...else: integer divide by R (2)
          i  - 1-based index of first occurrence of N in that
           ’ - decrement
  • \$\begingroup\$ For case three where \$N = 1\$ and \$M = 3\$ this code gives result \$2\$. The expected result is \$3\$. I hope you will be able to figure out this case :) \$\endgroup\$ Jun 18, 2020 at 19:51
  • 1
    \$\begingroup\$ OK sorted it. Thanks for spotting that. \$\endgroup\$ Jun 18, 2020 at 23:28
  • 2
    \$\begingroup\$ Why less than 16 bytes, specifically? \$\endgroup\$
    – Shaggy
    Jun 18, 2020 at 23:41
  • 1
    \$\begingroup\$ Found a few different solutions for 16 along the way. \$\endgroup\$ Jun 19, 2020 at 1:31

Japt, 15 14 bytes

Heading tag now includes the completely unnecessary space SE are forcing on us for no good reason

Well, seeing as everyone else is taking Arnauld's approach ...! Be sure to +1 him if you're +1ing this.

Takes input in reverse order.


Try it

>V?¢ÌÒß°Uz:UnV     :Implicit input of integers U=M and V=N
>V                 :Is U greater than V
  ?                :If so
   ¢               :  Convert U to base-2 string
    Ì              :  Get last character
     Ò             :  Subtract the bitwise negation of
      ß            :  A recursive run of the programme with argument U (V remains unchanged)
       °U          :    Increment U
         z         :    Floor divide by 2
          :        :Else
           UnV     :  U subtracted from V
  • 2
    \$\begingroup\$ The missing space in your header is an offense to our new Commonmark overlords! \$\endgroup\$
    – Arnauld
    Jun 18, 2020 at 15:02
  • \$\begingroup\$ What missing space, @Arnauld? Noticed it's not being formatted; I'm guessing something's broken in their parser. \$\endgroup\$
    – Shaggy
    Jun 18, 2020 at 15:21
  • \$\begingroup\$ Although, it is being formatted in other solutions. Retyped mine from scratch, still the same. Tried h2 instead, still the same. :\ \$\endgroup\$
    – Shaggy
    Jun 18, 2020 at 15:23
  • \$\begingroup\$ Our site has been migrated to CommonMark yesterday. The space after a # is now mandatory. \$\endgroup\$
    – Arnauld
    Jun 18, 2020 at 15:23
  • 1
    \$\begingroup\$ Ah. Well, that's seems to be a pretty moronic and unnecessary change, particularly the change to headings. \$\endgroup\$
    – Shaggy
    Jun 18, 2020 at 15:25

05AB1E, 18 bytes


Inspired by @Arnauld's JavaScript answer, so make sure to upvote him!

Try it online or verify all test cases.


[         # Start an infinite loop:
 Ð        #  Triplicate the pair at the top
          #  (which will use the implicit input in the first iteration)
  Æ       #  Reduce it by subtracting (N-M)
   d      #  If this is non-negative (>=0):
    #     #   Stop the infinite loop
  `       #  Pop and push both values separated to the stack
   D      #  Duplicate the top value `M`
    É     #  Check if it's odd (1 if odd; 0 if even)
      ½   #  If it's 1: increase the counter_variable by 1
     D    #  (without popping by duplicating first)
     +    #  Add this 1/0 to `M`
      ;   #  And halve it
       ‚  #  Then pair it back together with the `N`
 ¼        #  At the end of each iteration, increase the counter_variable by 1
}Æ        # After the infinite loop: reduce by subtracting again (N-M)
  ¾+      # And add the counter_variable to this
          # (after which the result is output implicitly)

perl -alp, 62 bytes


Try it online!

This uses the same logic as most other solutions.


Charcoal, 24 bytes


Try it online! Link is to verbose version of code. Takes inputs in the order M, N. Horribly inefficient breadth-first search, so don't bother putting in large numbers. Explanation:


Input M.


Push N to the predefined empty list.


Repeat until M is present in the list...


... concatenate the decremented list with the doubled list.


Calculate the number of concatenations.


Batch, 153 bytes

@echo off
@if %n%==%2 echo %c%&exit/b
@if %q%==0 if %r% lss %p% set/an=n*2+2
@goto l


set /a n=%1, c=0

Initialise n from the first parameter and clear the loop count.

if %n% == %2 echo %c% & exit /b

Output the count once the target in the second parameter is reached.

set /a " c += 1, p = ~-%2 / n + 1, q = p & p - 1, r = n * p - %2, n -= 1
  • Increment the loop count
  • Calculate the number of advances needed
  • Calculate how near to the target advances would get
  • Assume that we'll fall back
if %q% == 0 if %r% lss %p% set /a n = n * 2 + 2

If the advances would get near to the target then undo the fall back and advance instead.


bc, 61 bytes

define f(n,m){if(n>=m)return n-m;return 1+m%2+f(n,(m+m%2)/2)}

Try it online!

Given n, and m, return n - m if n is greater than or equal to m. Else, it returns 1 plus 1 (if m is odd), plus the result of (n, m / 2), with the division rounded upwards. The latter is done with a recursive call.


Befunge-98, 75 bytes

The program keeps a running total of moves at (0, 0) and remembers N at (1, 0). It definitely could be golfed some more.

2/1  v  >0g+.@ >^   >
1+2/2v  ^0-\g10<    >

Try it online! Edit: I had to add some extra arrows for it to run on TIO for some reason. See comments.

I used the logic from Arnauld's JavaScript answer.

  • \$\begingroup\$ Do you have a TIO link with an example? If I try that program in TIO, I can't find an input where the program finishes within a minute. Even simple cases like 1 1, or 1 2 seem to run forever. \$\endgroup\$
    – Abigail
    Jun 18, 2020 at 0:08
  • \$\begingroup\$ @Abigail I spent awhile trying to get it to run in TIO, but couldn't identify the issue (wrapping around doesn't work correctly?). It works fine locally and also on: qiao.github.io/javascript-playground/… \$\endgroup\$
    – Dallan
    Jun 18, 2020 at 0:53
  • \$\begingroup\$ That link is to a Befunge-93 interpreter, not Befunge-98. If I use TIO with Befunge-93, I have some success, that is, some inputs give the right answer, but some inputs seem to get stuck in a loop trying to divide by 0. 666 6666 for instance TIO link \$\endgroup\$
    – Abigail
    Jun 18, 2020 at 10:06
  • \$\begingroup\$ Ah, I found the problem. You are writing the input numbers in the Befunge space. But they take a signed tinyint. The TIO interpretation is strict, and putting a 666 into a cell means -102 is actually put there. The link you post allows writing large numbers into cells. \$\endgroup\$
    – Abigail
    Jun 18, 2020 at 10:10
  • \$\begingroup\$ @Abigail Thanks for looking into this. According to the specification, Funge-98 programs can have values up to 2bil. I only use Funge-93 commands, but run in Funge-98 to handle the large characters \$\endgroup\$
    – Dallan
    Jun 18, 2020 at 13:09

Erlang (escript), 65 bytes

Port of Arnauld's answer.

f(X,Y)->if X>Y->X-Y;true->1+(Y rem 2)+f(X,(Y+(Y rem 2))div 2)end.

Try it online!


J, 22 bytes

A port of RGS' APL answer with J's hooks and forks.


Try it online!


Your Answer

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

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