Java 1D Array: Solved

 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.

Function Description

Complete the canWin function in the editor below.

canWin has the following parameters:

• int leap: the size of the leap
• int game[n]: the array to traverse

Returns

• boolean: true if the game can be won, otherwise false

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:

1. The first line contains two space-separated integers describing the respective values of  and .
2. 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 .

Sample Input

STDIN           Function
-----           --------
4               q = 4 (number of queries)
5 3             game[] size n = 5, leap = 3 (first query)
0 0 0 0 0       game = [0, 0, 0, 0, 0]
6 5             game[] size n = 6, leap = 5 (second query)
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:

1. 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.
2. For  and , we can walk to index  and then jump  units to the end of the array. Because we can win, we return true.
3. For  and , there is no way for us to get past the three consecutive ones. Because we cannot win, we return false.
4. For  and , there is no way for us to get past the one at index . Because we cannot win, we return false.

Solution:

import java.util.*;

public class Solution {

   

    public static boolean canWin(int leap, int[] game, int i) {

        int gameLen = game.length;

        if(i>=gameLen){

            return true;

        }

        if(i<0 || game[i]==1){

            return false;

        }

        game[i] =1;

        return canWin(leap, game, i+leap) ||

        canWin(leap, game, i+1) || canWin(leap, game, i-1);

    }

    public static boolean canWin(int leap, int[] game) {

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

   return canWin(leap, game, 0);

   

    }

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

    }

}