## Hackerrank Java 1D Array (Part 2) Solution

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

*Move Backward:*If cell exists*and*contains a , you can walk back to cell .*Move Forward:*- If cell contains a zero, you can walk to cell .
- If cell contains a zero, you can jump to cell .
- If you're standing in cell or the value of , 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 , , or as long as the destination index is a cell containing a . If the destination index is greater than , you win the game.

Given and , complete the function in the editor below so that it returns *true* if you can win the game (or *false* if you cannot).

**Input Format**.

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

The subsequent lines describe each query over two lines:

- The first line contains two space-separated integers describing the respective values of and .
- The second line contains space-separated binary integers (i.e., zeroes and ones) describing the respective values of .

**Constraints**.

- It is guaranteed that the value of is always .

**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 queries:

- For and , we can walk and/or jump to the end of the array because every cell contains a . Because we can win, we return
*true*. - For and , we can walk to index and then jump units to the end of the array. Because we can win, we return
*true*. - For and , there is no way for us to get past the three consecutive ones. Because we cannot win, we return
*false*. - For and , there is no way for us to get past the one at index . Because we cannot win, we return
*false*.

### Solution in java8

**Approach 1**.

```
import java.util.*;
public class Solution {
public static boolean canWin(int leap, int[] game) {
return isSolvable(leap, game, 0);
}
private static boolean isSolvable(int m, int[] arr, int i) {
if (i < 0 || arr[i] == 1) return false;
if ((i == arr.length - 1) || i + m > arr.length - 1) return true;
arr[i] = 1;
return isSolvable(m, arr, i + 1) || isSolvable(m, arr, i - 1) || isSolvable(m, arr, i + m);
}
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)) ? "YES" : "NO" );
}
scan.close();
}
}
```

**Approach 2**.

```
import java.util.*;
public class Solution {
public static boolean canWin(int leap, int[] game) {
return isSolvable(leap, game, 0);
}
private static boolean isSolvable(int m, int[] arr, int i) {
if (i < 0 || arr[i] == 1) return false;
if ((i == arr.length - 1) || i + m > arr.length - 1) return true;
arr[i] = 1;
return isSolvable(m, arr, i + 1) || isSolvable(m, arr, i - 1) || isSolvable(m, arr, i + m);
}
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)) ? "YES" : "NO" );
}
scan.close();
}
}
```

**Approach 3**.

```
import java.util.*;
public class SolutionArray {
public static boolean find_path(int leap, int[] game, int x) {
if (x < 0) {
return false;
}
if (x > game.length - 1) {
return true;
}
if (game[x] != 0) {
return false;
}
game[x] = 5;
if (find_path(leap, game, x + 1)) {
return true;
}
if (find_path(leap, game, x + leap)) {
return true;
}
if (find_path(leap, game, x - 1)) {
return true;
}
game[x] = 0;
return false;
}
public static boolean canWin(int leap, int[] game) {
return find_path(leap, game, 0);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int q = scan.nextInt();
for (int j = 0; j < q; j++) {
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)) ? "YES" : "NO" );
}
scan.close();
}
}
```