Algorithm to step over array elements as per the given condition

Question

I am practicing to solve this problem, and have gotten 5 test cases passed but some test cases are failing I am not able to figure out what's the issue in my algorithm. Although I tried with some test data from failed test cases, most of them are coming correctly but I believe some are incorrect hence leading to my algorithm failure. So If someone can give an insight on the correct way to implement this algorithm that would be very helpful or where am I going wrong in my implementation.

My Algo:

    1. Index for the move is at index '0' of string (say moving index)
    2. Loop over the string starting with index '1' of string:

       2.1. check if (moving index + leap) can outrun the array:

       2.2. If not then, check whether the character is 1 or 0 :

           2.2.1 Check for the number of '1's that are continuous, if they exceed the leap value then return false (as anyway we will not be able to jump).

           2.2.2 If its 0, then check whether its a zero after continuous '1's.

              If not so, continue moving forward one step at a time.

              If so, first try to skip over those continuous '1's by checking whether (moving index + leap) is allowed or not as per the rule.

              If not allowed, check in a while loop till what point we can move backwards one step at a time to get (moving index + leap) to satisfy.

              If not possible, return false.

I don't know whether this is an efficient way to implement solution of this sort of problem, any other possible methods are much appreciated.

code:

import java.util.*;

public class Solution {

    public static int leapStep(int index,int leap,int len,int[] game){
        if(game[index+leap]==0){
            index += leap;
        }
        return index;
    }

    public static boolean canWin(int leap, int[] game) {
        int index = 0;
        int len = game.length;
        int consecutiveLength=0;
        for(int i=1;i<len;){
            if(index+leap>len-1){
                return true;
            }
            if(game[i]==1){
                consecutiveLength++;
                if(consecutiveLength>=leap){
                    return false;
                }
                i++;
            }else{
                if(consecutiveLength==0){
                    index =i;
                    i++;
                }else{
                    if(index+leap<=len-1){
                        int tryLeap = leapStep(index,leap,len,game);
                        if(index < tryLeap){
                            index = tryLeap;
                            tryLeap =0;
                            i = index+1;
                        }else if(index>0 && game[index-1]==0 ){
                            boolean notViable = false;
                            while(index>0){
                                if(game[index-1]!=0)
                                    return false;
                                index -= 1;
                                i = index+1;
                                tryLeap = leapStep(index,leap,len,game);
                                if(index<tryLeap){
                                    index = tryLeap;
                                    i = index+1;
                                    tryLeap=0;
                                    notViable = false;
                                    break;
                                }
                                else{
                                    notViable = true;
                                }
                            }
                            if(notViable){
                                return false;
                            }
                        }else{
                            return false;
                        }
                    }
                    consecutiveLength=0;
                }
            }
        }//closing for
         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)) ? "YES" : "NO" );
        }
        scan.close();
    }
}

Answer 1

To me, a better approach is to solve this recursively as below (it passed all the tests):

public static boolean canWin(int[] array, int index, int leap) {
    // the only case when we lose
    if (index < 0 || array[index] > 0) {
        return false;
    } 

    // if you're standing in the last entry or (index + leap) >= array.length then win
    if ((index >= array.length - 1) || ((index + leap) >= array.length)) {
        return true;
    }

    // mark it as visited so that not to iterate over it again
    array[index] = 1;
    // check all 3 conditions then recursively again
    return canWin(array, index + 1, leap) || canWin(array, index - 1, leap) || canWin(array, index + leap, leap);
}

In the input below several pairs of lines are shown. The first element of each pair stands for leap and the second one for an array.

Input:

3

0 0 0 0 0

5

0 0 0 1 1 1

3

0 0 1 1 1 0

1

0 1 0

Output:

true

true

false

false

Explanation:

Let's say your current position is index.

1. If it's negative or the array value is larger than 0 then the game is lost. If it's the last position or index + leap reaches at least the length of the array then the game is won by definition.
2. Otherwise, the only possible moves from here could be index - 1 or index + 1 or index + leap. So, you repeat step 1 for each of the latter indices and take OR of the result because finding a single path is enough. Don't forget to set a value of the cell to 1 because it doesn't make sense to visit it the second time - we don't want to repeat the same moves over and over again and crash.

Answer 2

Your pseudo-code seems fine, but there a few mistake in your code, that may be the cause of your trouble.

• The least problematic first, if(index+leap<=len-1) inside your loop is useless, you can remove it without modify the behaviour of your algorithm. It is the case because you already checked it in the first line of the loop and entered an else keyword.
• This one is about your variables index and i. Their meaning isn't clear to me after a few complete read, and they look like the same. It might cause you trouble because you use the variable index inside your call to leapStep, but index is often one step behind i. It's confusing.

I did not found an example where your code fails.

Here is my solution HackerRank accepted. It is an iterative one, close to yours. Its principle is simple: starting from position 0, as we increase step by step our position, keep track of the positions you have access to (in variable memoTab, I removed the dp name as it can be frightening): if we are on a position we already reached before, then we can go to +1 or +leap. It would be enough if it wasn't allowed to backtrack and go the reverse direction. To deal with that, whenever we reach some 1s, I keep in memory the next 0. And if I encounter a position I can reach just after, I go back to that 0 and say I can go there.

Here is the code, first a little helper function that returns true if the game is finished. Given a game and an index it says if we can go to that index and write it to the memo.

    public static boolean check(int[] game, boolean[] memo, int index){
        if(index >= 0 && index < game.length){
            if(game[index] != 1){
                memo[index] = true;
            }
        }
        return index >= game.length;
    }

This is the solver function, it first reads the values, then starts looping.

    public static void solveOne(){
        int n = sc.nextInt();
        int leap = sc.nextInt();

        int[] game = new int[n];
        for (int i = 0; i < n; i++) {
            game[i] = sc.nextInt();
        }

        int index = 0;
        boolean[] memoTab = new boolean[n];
        for (int i = 0; i < n; i++) {
            memoTab[i] = false;
        }
        memoTab[0] = true;

        boolean rememberIndex0 = false;
        boolean gotoIndex0 = false;
        int index0 = 0;

        boolean finished = false;

We are done with the initialization, let's loop:

        while(index < game.length){
            // we encounter the first 0 after some 1, keep it in memory !
            if(rememberIndex0 && game[index] == 0){
                index0 = index;
                gotoIndex0 = true;
                rememberIndex0 = false;
            }

            // this index is an index we reached before, we can continue from here
            if(memoTab[index]){
                // we previously said we need to go back to a lower position
                if(gotoIndex0){
                    gotoIndex0 = false;
                    index = index0;
                    memoTab[index] = true;
                    continue;
                }
                // it's finished if either is true
                finished = check(game, memoTab, index + 1)
                        || check(game, memoTab, index + leap);

                if(finished) break;
            }

            //  if this position is a 1, then we will keep in memory the next 0
            if(game[index] == 1){
                rememberIndex0= true;
            }

            // don't forget incrementing
            index += 1;
        }

        System.out.println(finished?"YES":"NO");
    }