Let’s play a game on an array! You’re standing at index 0 of an n-element array named game. From some index i(where 0<=i<n ), you can perform one of the following moves:

*Move Backward:*If cell i-1 exists*and*contains a 0, you can walk back to cell i-1.- Move Forward:
- If cell i+1 contains a zero, you can walk to cell i+1 .
- If cell i+leap contains a zero,you can jump to cell i+leap.
- If you’re standing in cell n-1 or the value of i+leap>=n, you can walk or jump off the end of the array and win the game.

- In other words, you can move from index to index i+1,i-1 , or i+leap as long as the destination index is a cell containing a 0. If the destination index is greater than , you win the game.
- Given leap and game,complete the function in the editor below so that it return true if you win the game(or false if you cannot).

**Input Format**

The first line contains an integer, q, denoting the number of queries (i.e., function calls).

The 2.q subsequent lines describe each query over two lines:

- The first line contains two space-separated integers describing the respective values of n and leap.
- The second line contains n space-separated binary integers (i.e., zeroes and ones) describing the respective values of game_0,game_1,…,game_n-1.

**Constraints**

1<=q<=5000 2<=n<=100 0<=leap<=100

It is guaranteed that the value of game[0] is always 0.

**Output Format**

Return *true* if you can win the game; otherwise, return *false*.

**Sample Input**

```
4
5 3
0 0 0 0 0
6 5
0 0 0 1 1 1
6 3
0 0 1 1 1 0
3 1
0 1 0
```

**Sample Output**

```
YES
YES
NO
NO
```

**Explanation**

We perform the following q=4 queries:

- For game=[0,0,0,0,0] and leap=3, we can walk and/or jump to the end of the array because every cell contains a 0. Because we can win, we return
*true*. - For game=[0,0,0,1,1,1] and leap=5, we can walk to index 1 and then jump i+leap=1+5=6 units to the end of the array. Because we can win, we return
*true*. - For game=[0,0,1,1,1,0] and leap=3, there is no way for us to get past the three consecutive ones. Because we cannot win, we return
*false*. - For game=[0,1,0] and leap=1, there is no way for us to get past the one at index 1 . Because we cannot win, we return
*false*.

**Solution.java**

import java.util.*; public class Solution { //fetching position containing zero public static int[] getzeroposi(int[] game){ int[] zeroarry=new int[game.length]; for(int j=0,k=0;j<game.length;j++){ if(game[j]==0){ zeroarry[k]=j+1; //+1 to avoid 0 k++; } } return zeroarry; } public static boolean findposarr(int[] zeropos,int pos){ for(int j=0;j<zeropos.length;j++){ if(zeropos[j]==pos){ return true; } } return false; } public static boolean canWin(int jumpLength, int[] game,int currentPos,int lastJumpPos) { boolean didWin=false; int range=currentPos; while(range<game.length-1 && game[1+range]==0){ range++; } if(range==game.length-1){ return true; } int lowRange=range; while(lowRange>lastJumpPos && game[lowRange-1]==0 && (lowRange+jumpLength)>range+1){ lowRange--; } currentPos=lowRange; for(int i=currentPos;i<=range;i++){ if((i+jumpLength)<game.length && game[i+jumpLength]==0 && jumpLength!=0){ didWin=canWin(jumpLength,game,i+jumpLength,i); } if(didWin || (i+jumpLength)>=game.length||(i+1)>=game.length){ didWin=true; break; } } return didWin; // Return true if you can win the game; otherwise, return false. // return false; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int q = scan.nextInt(); while (q-- > 0) { int n = scan.nextInt(); int leap = scan.nextInt(); int[] game = new int[n]; for (int i = 0; i < n; i++) { game[i] = scan.nextInt(); } System.out.println( (canWin(leap, game,0,0)) ? "YES" : "NO" ); } scan.close(); } }

Thank You.

I loved your blog.Really looking forward to read more. Will read on…