Return to Answer

• 13.8k
• 12
• 57
• 127

• 647
• 1
• 6
• 14

• 647
• 1
• 6
• 14

Here's my solutions (in C#, can be "easily" adapted to C):

I started with a recursive solution, that breaks the big problem to smaller ones (basically defers the decision on complicated matters until the simpler matters are solved) - there is basically 2 base cases - either the tower is bigger than remaining size (return true) or it's 0 (return false). For the rest you have to recurse. The loop starts from the farthest you can go from the first tower (recurse for that tower etc.), and then goes down... up to making just 1 step:

 public static bool IsHoppableNaive(int[] array, int len)
 {
 if (array[0] >= len)
 return true;
 if (array[0] <= 0)
 return false;
 bool ret = false;
 for (int i = array[0]; i >= 1; i--)
 {
 var newArray = new int[len - i];
 Array.Copy(array, i, newArray, 0, len - i);
 ret = ret || IsHoppableNaive(newArray, len - i);
 if (ret) // optimization - no point in continuing if already true...
 break;
 }
 return ret;
 }

Time complexity of this is 2^(n-1)... So this could be very inefficient. That is why it can be improved with Dynamic Programming.

For DP solution, I first solved this theoretically by constructing a table of n x n . The way you fill this table is for each row you take the tower number and set the subsequent columns to true, (representing can I reach the next tower? and not can I reach the current tower, as you are already in it). Otherwise you give it false (for the first row), and for any subsequent row you take whatever is in the upper row.

enter image description here

the * are ones that are true thanks to their above row, and not for the actual number.

Here's the code:

 public static bool IsHoppableDP(int[] array, int len)
 {
 bool[,] dp = new bool[len, len];
 for (int i = 0; i < len; i++)
 {
 for (int j = i; j < len; j++)
 {
 if (j < i + array[i])
 dp[i, j] = true;
 else if (i > 0)
 dp[i, j] = dp[i - 1, j];
 else
 dp[i, j] = false;
 }
 }
 return dp[len - 1, len - 1];
 }

So, here we can save from bad cases, but even good cases will take n + (n-1) + (n-2) + ... + 1 - which is n*(n+1)/2 ... basically also O(n^2). Which is a major improvement over the O(2^n)

Finally there is the "Simple" solution shown here, without the helper method/function.

The "simple" solution (it was actually far less simple to write that tricky getNext function) seems to offer the best time and space complexity. It basically uses some "heuristics", i.e. we know that the best tower to jump to is the one that offers the farthest range. The farthest range can be computed by adding the current index with the current value. We just have to be careful not to get out-of-bounds Argument-Exception...

Here's the code:

 public static bool IsHoppableSimple(int[] array, int len)
 {
 int current = 0;
 while (true)
 {
 if (current >= len)
 return true;
 if (array[current] == 0)
 return false;
 current = bestNextStep(current, array, len);
 }
 }
 private static int bestNextStep(int current, int[] array, int len)
 { 
 int best = current + array[current]; // Assuming the current farthest is the best 
 
 for (int i = current; i < current + array[current]; i++) // find the actual best
 {
 if (i + array[i] > len)
 return i + array[i]; // caution against getting outside of the bounds of the array
 if (i + array[i] > best)
 best = i + array[i];
 }
 return best;
 }

Time complexity here is O(n) [we only traverse the array once], and space complexity is O(1) [we do everything in place].