PROBLEM LINK:
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.