In this HackerRank java Array (Part 2) problem in the java programming language you have Given leap and game, complete the function in the editor below so that it returns true if you can win the game (or false if you cannot).

HackerRank Java 1D Array (Part 2) problem solution


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