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