# HackerRank Java 1D Array (Part 2) problem solution

In this HackerRank java Array (Part 2) problem in the java programming language 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 i 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 n-1, you win the game.

## HackerRank Java 1D Array (Part 2) problem solution.

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = Integer.parseInt(scanner.nextLine());
for (int i = 0; i < t; i++) {
int n = scanner.nextInt();
int m = scanner.nextInt();
//System.out.println(n + " " + m);
int[] arr = new int[n];
for (int j = 0; j < n; j++) {
arr[j] = scanner.nextInt();
//System.out.print(arr[j]);
}
//System.out.println();
solve(n,m,arr);
}
}

public static void solve(int n, int m, int[] arr) {
if (solve(n,m,arr,new boolean[n],0)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}

public static boolean solve(int n, int m, int[] arr, boolean[] visited, int curr) {
if (curr + m >= n || curr + 1 == n) {
return true;
}

boolean[] newVisited = new boolean[n];
for (int i = 0; i < n; i++) {
newVisited[i] = visited[i];
}

boolean s = false;
if (!visited[curr+1] && arr[curr+1] == 0) {
newVisited[curr+1] = true;
s = solve(n,m,arr,newVisited,curr+1);
}
if (s) {
return true;
}
if (m > 1 && arr[curr+m] == 0 && !visited[curr+m]) {
newVisited[curr+m] = true;
s = solve(n,m,arr,newVisited,curr+m);
}
if (s) {
return true;
}
if (curr > 0 && arr[curr-1] == 0 && !visited[curr-1]) {
newVisited[curr-1] = true;
s = solve(n,m,arr,newVisited,curr-1);
}
return s;
}
}```

## Second solution in java8 programming.

```import java.util.*;

public class Solution {

public static boolean canWin(int leap, int[] game) {
VirtualPlayer v = new VirtualPlayer(leap, game);
v.tick();
return v.winnable;

}
static class VirtualPlayer {
private int pos = 0; //pos-ition
private int lp; //lp means leap
private int[] map;
boolean winnable = false;
public VirtualPlayer(int lp, int[] map) {
this.lp = lp; //gets the values from the canWin function
this.map = map;

}
private void moveup() {
if (map[pos + 1] == 0) {
pos++;
tick();
}

}

private void movedown() {
if ((pos - 1) >= 0 && map[pos - 1] == 0) {
map[pos] = 1;
pos--;
tick();
}

}

private void jump() {
if ((pos + lp) < map.length) {
if (map[pos + lp] == 0) {
int posold = pos;
pos = pos + lp;
tick();
pos = posold;
}
}

}
void tick() {
//System.out.println("im at:"+pos);
if (pos == (map.length - 1) || ((pos + lp) >= map.length)) {
winnable = true;
}
else {
this.moveup();
if (lp != 0) {
this.jump();
} //cant jump 0 steps!
this.movedown();
}

}

}

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();
}
}```

### Third solution

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
int caseCount = scanner.nextInt();
for(int ii=0; ii<caseCount; ++ii)
{
int arraySize = scanner.nextInt();
int jumpSize = scanner.nextInt();
int[] array = new int[arraySize];
for(int jj=0; jj<arraySize; ++jj) array[jj] = scanner.nextInt();
// --
boolean solvableGame = solveGame(array, jumpSize, 0, new boolean[array.length]);
System.out.println(solvableGame?"YES":"NO");
}
}
public static boolean solveGame(int[] array, int jumpSize, int position, boolean[] testedPositions)
{
// System.out.println("solveGame:"+position);
if(position < 0) return false;
if(position >= array.length) return true;
if(testedPositions[position]) return false;
if(array[position]==1) return false;
// --
// -- test jump back case is pointless
// -- which just repeat the last position
// --
testedPositions[position]=true;
return solveGame(array, jumpSize, position+jumpSize, testedPositions)
|| solveGame(array, jumpSize, position+1, testedPositions)
|| solveGame(array, jumpSize, position-1, testedPositions);

}
}```