We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Java
  3. Data Structures
  4. Java 1D Array (Part 2)
  5. Discussions

Java 1D Array (Part 2)

Sort by

recency

|

625 Discussions

|

  • zhengjiawen44
     + 1 comment

    reposting a solution from @kdubey2181, that I think is the most elegant and simple way to solve this problem.

    import java.util.*;

public class Solution {

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

        int lastIndex = game.length-1;
        
        //did you win by jumping over the last index?
        if(position>lastIndex){
            return true;
        }
        
        //did you reverse out of bounds or meet a obstacle?
        if(position<0 || game[position]==1){
            return false;
        }
        
        //mark current position as explored
        game[position] = 1;
        
        //Explore all possible solutions from current position
        return canWin(leap, game, position+1) || canWin(leap, game, position-1) || canWin(leap, game, position+leap);
    }

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

  • aniketgupta2514
     + 1 comment

    whats wrong with my iterative approach can anyone point out?

            int n = game.length;
        int pointer = 0;
        while(pointer<=n){
            if(pointer+leap>=n || pointer+1>=n) return true;
            if(pointer+leap<n && game[pointer+leap]==0){
                pointer+=leap;
            }
            else if(pointer+1<n && game[pointer+1]==0){
                pointer+=1;
            }
            else if(pointer-1>=0 && game[pointer-1]==0){
                pointer-=1;
            }
            else{
                return false;
            }
            game[pointer]=1;
        }
        return true;

  • gracelyganta
     + 0 comments
    import java.util.*;

public class Solution {

    public static boolean find_path(int leap, int[] game, int x) {
        if (x < 0) {
            return false;
        }

        if (x > game.length - 1) {
            return true;
        }

        if (game[x] != 0) {
            return false;
        }

        game[x] = 5;

        if (find_path(leap, game, x + 1)) {
            return true;
        }
        if (find_path(leap, game, x + leap)) {
            return true;
        }
        if (find_path(leap, game, x - 1)) {
            return true;
        }

        game[x] = 0;

        return false;
    }

    public static boolean canWin(int leap, int[] game) {
        return find_path(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();
    }
}

  • praveen2004soni
     + 0 comments

    Why only test case 0 is correct not any other

    import java.util.*;

    public class Solution {

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


    int w =0;


    while( w < game.length){

        int setValue = 0; 

       if ( w + leap > game.length ){
           break;
       }


       else if(game[w+1]==0){
            w++;
        }
        else if(game[w+1]==1){

         if( w+leap< game.length && game[w+leap] == 0 ){
             w+=leap;
         }

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

    }

  • n4m774r_d
     + 0 comments
    class Rules {
    public static boolean hasZero(int value)
        {return String.valueOf(value).contains("0");}
        
    public static boolean finish(int idx, int leap, int[] game)
        {return (idx + 1 > game.length - 1 ||
                idx + leap > game.length - 1);}
                
    public static boolean goBack(int idx, int[] game)
        {return (idx != 0 && hasZero(game[idx - 1]));}
        
    public static boolean goForward(int idx, int[] game)
        {return hasZero(game[idx+1]);}
        
    public static boolean leap(int idx, int leap, int[] game)
        {return hasZero(game[idx+leap]);}
}
public class Solution {

    public static boolean canWin(int idx,int leap, int[] game) {
        if (Rules.finish(idx, leap, game)) return true;
        game[idx] = 1;
        boolean canWin = 
        Rules.goForward(idx, game) && canWin(idx + 1, leap, game) ||
        Rules.leap(idx, leap, game) && canWin(idx + leap, leap, game) ||
        Rules.goBack(idx, game) && canWin(idx - 1, leap, game);
        game[idx] = 0;
        return canWin;
    }

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