Assuming initial position is (1, 1), find out if you can reach (x, y) by the following given rules at each step

Question

You are given the coordinates (x,y). Initially, you are at (1,1) and are required to go to (x,y) using the following rule: If the current position is (a,b) then in the next move, you can move only to (a+b,b) or (a,a+b). Write a program to check if you can reach (x,y) using only the described moves.

I have tried to solve this problem that I mentioned above in Java through recursion. But the program was not working for some test cases. I could not find what is wrong. But I know it is a brute force method.

import java.util.*;
class Solution{
    static boolean sol(int a, int b, int x, int y){
        if( a == x && b == y)
            return true;
        else if(a > x || b > y)
            return false;
        else{
            if(sol(a+b, b, x, y)) return true;
            if(sol(a, a+b, x, y)) return true;
        }
        return false;
    }
    static String ans(int x, int y){
        if(sol(1, 1, x, y)) return "Yes";
        return "No";
    }
    public static void main(String[] args) {
        int x, int y;
        Scanner sc = new Scanner(System.in);
            x = sc.nextInt();
            y = sc.nextInt();
            System.out.println(ans(x, y));
        
    }
    
}

This is the code that I wrote. Can someone tell me an efficient for this solving this and tell me what's wrong with my code?

Answer 1

Take a look at:

if(sol(a, a+b, x, y)) return false;

That condition should return true as mentioned in the problem that "you can move only to (a+b,b) or (a,a+b)".

import java.util.*;
class Solution{
    static boolean sol(int a, int b, int x, int y){
        if( a == x && b == y)
            return true;
        else if(a > x || b > y)
            return false;
        else{
            if(sol(a+b, a, x, y)) return true;
            if(sol(a, a+b, x, y)) return true;
        }
        return false;
    }
    static String ans(int x, int y){
        if(sol(1, 1, x, y)) return "Yes";
        return "No";
    }
    public static void main(String[] args) {
        int x,y;
        Scanner sc = new Scanner(System.in);
            x = sc.nextInt();
            y = sc.nextInt();
            System.out.println(ans(x, y));
        
    }
    
}

OPTIMAL APPROACH:

Use a two-dimensional matrix (x * y) to know whether that cell is visited or not and if visited to store the result.

Not visited -> -1

visited and possible to reach to (x,y) from that position -> 1

visited and possible to reach to (x,y) from that position -> 0

import java.util.*;
class Solution{
    
    static boolean sol(int a, int b, int x, int y, int[][] dp){
        if( a == x && b == y)
            return true;
        else if(a > x || b > y)
            return false;
        else if(dp[a][b] == 1)
            return true;
        else if(dp[a][b] == 0)
            return false;
        else if(sol(a+b, a, x, y, dp) || sol(a, a+b, x, y, dp)){
                dp[a][b] = 1;
                return true;
        }
        dp[a][b] = 0;
        return false;
    }
    
    static String ans(int x, int y, int[][] dp){
        if(sol(1, 1, x, y, dp)) return "Yes";
        return "No";
    }
    
    public static void main(String[] args) {
        int x,y;
        int[][] dp;
        
        Scanner sc = new Scanner(System.in);
        x = sc.nextInt();
        y = sc.nextInt();
        
        dp = new int[x+1][y+1];
        for(int[] row : dp)
            Arrays.fill(row,-1);
        
        System.out.println(ans(x, y, dp));
        
    }
    
}