I am trying to solve this problem on HackerRank for hours. The basic problem statement is as follows:
You have a 1D array consisting only of 0s and 1s . You start at the 0th index. Lets assume the size of array to be n. You win if you can reach beyond the scope of array(i.e to an index > n-1). But you can only move in two ways:
ALSO, YOU CAN ONLY STEP ON AN ELEMENT WITH VALUE 0. The value at 0th index is known to be 0. (so you start at a valid position)
'm' is provided as an input and it can be any value between 0 and 100 inclusive. The array size can be any value between 2 and 100 inclusive.
The program should print "YES" if a win is possible. else "NO".
I tried solving it using a backtracking algorithm in Java. But it gets rejected for most test cases.
Please help me. Thanks in advance.
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int[] array = new int[n];
for(int i=0;i<n;i++){
array[i]=sc.nextInt();
}
if(m<2){
for(int i=0;i<n;i++){
if(array[i] == 1){
System.out.println("NO");
break;
}
}
System.out.println("YES");
}
else{
if(isSolvable(array,0,m,n))
{System.out.println("YES");}
else
{System.out.println("NO");}
}
}
static boolean isSolvable(int[] array,int x,int m,int n){
if(x>n-1){
//System.out.print(x + " ");
return true;
}
if(array[x] == 1) return false;
if(isSolvable(array,x+m,m,n)){
//System.out.print(x + " ");
return true;
}
if(isSolvable(array,x+1,m,n)){
//System.out.print(x + " ");
return true;
}
return false;
}
}
I didn't do this with backtracking, but just recursion, and I was able to solve the problem and get all test cases correct. The code that you've posted also doesn't do any backtracking. I also see that in your conditions, you're missing the condition to move backward by 1, which would cause you to fail some cases.
Eg: 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 with m=5.
With the above example, first you jump to x+m, then try x+m again, then try x+1, otherwise you get out.
To break this test case down:
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1
^ x+m True
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1
^ x+m False
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1
^ x+1 False
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1
^ x+1 False
With your code, you would return false where instead to solve this, you would need to do the following:
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1
^ x+m
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1
^ x-1
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1
^ x+m
Then two more x+m's to complete it to return true.
To complete this using your code, you need to add the condition to move back one space, BUT when doing so, you could incorporate an endless recursive loop Eg: (-1+1-1+1-1+1) which will cause a stackoverflow. One of the things I would suggest including would be a boolean array to hold memory of which spots you've seen before.