Digit Wood

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.

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

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

SOLUTION : – 1

import java.util.*;

public class Solution {

    public static boolean canWin(int leap, int[] game, int start) {
        for(int i = start; i < game.length; i++) {
            game[i] = 1;
            if(i + 1 == game.length || i + leap >= game.length) break;
            if(game[i + leap] == 0) {
                int j = i + leap;
                while(j > 0 && game[j - 1] == 0) --j;
                if(canWin(leap, game, j)) return true;
            }
            if(game[i + 1] != 0) return false;
        }
        return true;
    }

    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, 0)) ? "YES" : "NO");
        }
        scan.close();
    }
}

SOLUTION : – 2

To optimize the code, we can make a few changes to improve its efficiency:

1. Avoid Recalculating Results: Use a boolean array to keep track of visited indices to avoid recalculating the result for the same index.
2. Exit Early on Success: If we reach the end of the array or can make a leap to reach beyond the array, return true immediately.
3. Use a Queue for BFS: Instead of recursion, use a queue for BFS traversal to reduce the risk of stack overflow for large inputs.

Here’s the optimized code:

import java.util.*;

public class Solution {

    public static boolean canWin(int leap, int[] game) {
        if (game == null || game.length == 0) return false;

        int n = game.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (current + leap >= n || current == n - 1) {
                return true;
            }

            if (current - 1 >= 0 && game[current - 1] == 0 && !visited[current - 1]) {
                queue.offer(current - 1);
                visited[current - 1] = true;
            }

            if (game[current + 1] == 0 && !visited[current + 1]) {
                queue.offer(current + 1);
                visited[current + 1] = true;
            }

            if (game[current + leap] == 0 && !visited[current + leap]) {
                queue.offer(current + leap);
                visited[current + leap] = true;
            }
        }

        return false;
    }

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

FOLLOW FOR MORE QUESTIONS AND SOLUTIONS | DIGIT WOOD