Solution to HackerRank’s: Jumping on the Clouds

Julio Santana
3 min readJul 24, 2021

The problem is as follow:

There is a new mobile game that starts with consecutively numbered clouds. Some of the clouds are thunderheads and others are cumulus. The player can jump on any cumulus cloud having a number that is equal to the number of the current cloud plus or . The player must avoid the thunderheads. Determine the minimum number of jumps it will take to jump from the starting position to the last cloud. It is always possible to win the game.

For each game, you will get an array of clouds numbered if they are safe or if they must be avoided.

My Solution:

The problem can be solved in many ways, being some of them less performant than other (Ex. Calculate all path to the goal and extract the minimum)

In this case, we could try a greedy algorithm and try to prove that taking the best local solution (jumping 2 positions every-time is possible will lead us to the best global solution) Let’s try to prove it.

Jumping clouds!

Proof:

I’ll try to prove it by absurd reduction. Let’s assume that on jump j the player can arrive either to position n or position n+1. Also if he choose to go to position n he will need to finish only p1 jumps and if he choose position n+1 he will need p2, being p1 < p2.

So he will go to position n, since he will arrive faster to the end from there. Now, being in position n, he can move either to position n+1 or position n+2.

If he moves to position n+1 he will need from this point on p1–1 jumps to reach the end, and we know that from this position the minimum number of jumps needed is p2. So we could say that p2 = p1 -1 and at the same time p1 <p2 which is a contradiction.

If he moves to position n+2, he will be one position ahead of n+1, so this mean that a player in position n+1 could be in his same position in only one jump. This means that p1–1 = p2–1 and p1<p2 which is again a contradiction.

So this proof that the player can’t arrive faster selecting to move to n, instead of n+1. Our best shot is to always try to move to the longest distance in the current step.

Also something important is that thunderheads biggest length is 1, and they can be only jumped with movements of length 2.

Having said that, the implementation could look as follow

public static int jumpingClouds(List<Integer> clouds) {
int[] possibleJumps = {2, 1};
int currentIndex = 0;
int numberOfJumps = 0;
final int sizeOfClouds = clouds.size();

while(currentIndex < sizeOfClouds - 1) {
for(int i = 0; i < possibleJumps.length; i++) {
// if the next biggest possible move is inside the clouds lengths and is a cumulus, we go there
if(currentIndex + possibleJumps[i] < sizeOfClouds && clouds.get(currentIndex + possibleJumps[i]) == 0) {
currentIndex += possibleJumps[i];
numberOfJumps++;
break;
}
}
}

return numberOfJumps;
}

--

--