Codesignal Solution: Minimum Jump To Reach End

Original Problem

There are several points on a straight line, and you're standing at point 1. Your task is to get to the last point in the minimum number of jumps. There are two constraints on the jumps you can make:

1. the first and last jumps should be of size 1;
2. the absolute difference between the lengths of two consecutive jumps should be less than or equal to 1.

Return the minimum number of jumps you should make to get from the first point to the last one under the conditions given above.

Example

For n = 14, the output should be

minJumpToReachEnd(n) = 7.

Here's the fastest way to get to the last point:

Input/Output

• [time limit] 4000ms (py)

• [input] integer points

  The number of points.

  Constraints:
  
  5 ≤ points ≤ 10⁹.

• [output] integer

  The minimum required number of jumps.

Solution

In order to minimize the number of jumps, it's necessary to increase the stepwidth as much as possible. I was thinking of this problem in 2D, drawing the current stepwidth on the y-axis. That means that for 5 jumps, we can reach a height of two at most:

When you think about it, you go up on the left, keep going and go down on the right side afterwards. So, the jump steps can be modeled like this, with the derivation of the final height:

\[ \begin{array}{rl} & 2\sum\limits_{k=1}^h k - h &\leq n - 1\\ \Leftrightarrow & h(h+1)-h &\leq n-1\\ \Leftrightarrow & h^2 & \leq n-1\\ \Rightarrow & h = \lfloor\sqrt{n-1}\rfloor \end{array} \]

Okay, that's pretty cool. The number of elements we cover with this pattern is:

\[ s = 2\sum\limits_{k=1}^h k - h = h^2 \]

We know that the sum over the final height is less or equal to the required width, namely \(h^2\leq n\). With 5 points, it was closed perfectly, but let's see how it looks with 9 points:

The gap is large enough to fill another \(h\)-block in. The number of such blocks can be calculated as:

\[r = \left\lfloor \frac{n-1-s}{h} \right\rfloor \]

The \(r h\) value repairs the fact, that we initially reduced the double sum by \(h\), as it's possible to have only one jump on the highest level and then back down. When we look at the graph of 6 points, we see a similar thing as with 9:

We still have one jump left, with a width \(< h\), which can be added on the respective level when going down on the right. The gap-width is simply \(n-1-s-rh\). In order to make this a binary value of 0 or 1, we divide the value by the maximum gap-width of \(h-1\):

\[ g = \left\lceil \frac{n-1-s-rh}{h-1} \right\rceil= -\left\lfloor \frac{rh-n+1+s}{h-1} \right\rfloor \]

That means that the final number of jumps is simply the number of jumps \(h\) plus \(h\) on the right, reduced by one for the upper level plus the boolean \(g\) if a gap \(< h\) is there plus \(r\), the number of additional \(h\) elements on the top:

\[\begin{array}{rl} j &= 2h-1 + g + r\\ &= 2h-1 -\left\lfloor \frac{\left\lfloor \frac{n-1-h^2}{h} \right\rfloor\cdot h-n+1+h^2}{h-1} \right\rfloor + \left\lfloor \frac{n-1-h^2}{h} \right\rfloor \end{array}\]

Implemented in JavaScript, the following code can be brought up:

function minJumpToReachEnd(n) {
 n--;
 var h = Math.floor(Math.sqrt(n));
 var r = Math.floor(n / h - h);
 var g = Math.floor((h * (h + r) - n) / (h - 1));
 return 2 * h - 1 - g + r;
}

As there are these nasty floor-functions, it's hard to come up with a simplification. But when we look at the pattern generated by this function, we see the following: \(3,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8, ...\). Looking up this pattern, we'll see that it's a well known series, namely A000267 - just shifted by two. The formula for the number of jumps then can be simplified to:

\[j = \left\lfloor \sqrt{4 \cdot (n - 2) + 1} \right\rfloor = \left\lfloor \sqrt{4n - 7} \right\rfloor\]

Now the implementation is much prettier:

minJumpToReachEnd = n => Math.floor(Math.sqrt(4 * n - 7))

In order to get the idea, I present some more jump patterns with the \(n-1-h^2\) gaps in it:

#2:

#3:

#4:

#5:

#6:

#7:

#8:

#9:

#10: