SRTX16C - Editorial

PROBLEM LINK:

Practice

Contest

Author: Suraj Kumar

Tester: Priyanshu Jain

DIFFICULTY:

EASY

PREREQUISITES:

Arrays

PROBLEM:

Given an array of 0s and 1s. Traverse it from left end to right end by jumping on only zeroes. Jumping here

means that you can skip either 2, or, 1 or 0 number of zeroes. And also count the minimum number of such

jumps taken.

EXPLANATION:

We will try to simulate the whole scenario. We will traverse the array and keep a variable which will tell the

current position of Jack. We will also keep a count to keep the number of jumps taken.

Now starting at the first leaf. So, our current pointer will keep a value 0, since we start from first leaf which is at

index 0. Our count will be initialized to 0.

We can jump either one step, or two, or three in one chance. So, it will always be better to jump three blocks if

possible. So, we check for this condition. We can jump if the value of 3 rd element from the current value in the

array is 0 (magical leaf). If we cannot jump three blocks, then we try to jump two blocks. Jump if possible, else

check if you can jump at least a single step. If none of these three jump types is possible that means that you

cannot take a jump, and hence it is not possible to cross the river. It can be clearly seen that this condition

happens only when we have three or more consecutive ones (“pseudo-magical leaves”) in our array. And we can

break from whole loop and print “Never Give Up”.

With every jump taken, we will increment our jump counter by one. And also update our current position to

whatever position we jumped onto.

What will be the terminating condition for our simulation? Either we will find a position from where it is not

possible to jump (three or more consecutive ones). Or we have reached the final leaf, (i.e current == n-1).

PSEUDO-CODE:

current = 0, count = 0

flag = false

a[n] = a[n+1] = 1

while current < n-1 :

if a[current + 3] == 0 then:

current = current + 3

count = count + 1

else if a[current + 2] == 0 then:

current = current + 2

count = count + 1

else if a[current + 1] == 0 then:

current = current + 1

count = count + 1

else : //Jump is not possible, indicate it by the flag

flag = true

if flag

print : “Never Give Up\n”

else

print : count “\n”

It should be noted that we are accessing the array elements at index more than n. Make sure that your array is

large enough. And these last elements are initialized to 1.

For more clarity see the solutions given below.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

//