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

> 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?

Your question says:
> If the current position is (a,b) then in the next move, you can move only to (a+b,b) or (a,a+b).

Your mistakes are (highlighted inline in bold):

1. <code>if(sol(a+b, a, x, y)) return true; // a should be b</code>
2. <code>if(sol(a, a+b, x, y)) return false; // false should be true</code>

Correct both points with (highlighted inline in bold):

1. <code>if(sol(a+b, b, x, y)) return true;</code>
2. <code>if(sol(a, a+b, x, y)) return true;</code>

OR simplify by combining them:
<code>if(sol(a+b, b, x, y) || sol(a, a+b, x, y)) return true;</code>

With above suggestion full code would be:

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) || sol(a, a+b, x, y)) // fix applied here
            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));
    }
}

Edit for optimized solution than brute force

We are starting with (1, 1) and any next step of (a, b) is (a+b, b) or (a, a+b) so x > 0 and y > 0 is the required condition for any step (x, y).

Now, let's say,

Step k:   (a, b)  
Step k+1: (a2, b2) = (a+b, b) OR (a, a+b)

So if we want to derive step#k from step#k+1 then we can say (a, b) can be one of these two: (a2 - b2, b2) OR (a2, b2 - a2). We can easily remove one option as we know that a > 0 and b > 0.

• If (a2 - b2) > 0 then (a, b) must be (a2 - b2, b2).
• Similarly, if (b2 - a2) > 0 then (a, b) must be (a2, b2 - a2).
• If a2 == b2 (and not 1) then a2 - b2 and b2 - a2 will be 0 which is impossible as a > 0 and b > 0 is required condition.

So, we will start from destination (x, y) and try to reach (1, 1) by above observation in linear time. The gist will be:

static boolean solve(int x, int y) {
    if (x == 1 && y == 1) {
    	return true;
    }
    if (x == y || x < 1 || y < 1) {
    	return false;
    }
    if (x > y) {
    	return solve(x - y, y);
    } else {
    	return solve(x, y - x);
    }
}

Above solution is recursive and Ole V.V. has a good point in this answer about possible StackOverflowError if input numbers are large and stack memory allocation is relatively less. Based on his suggestion of the need of iterative solution, I am providing below gist for iterative approach:

static boolean solve(int x, int y) {
	while (x > 0 && y > 0) {
	    if (x == y) {
	        return (x == 1); // x and y can be same if they are 1, otherwise impossible
	    }
	    if (x > y) {
	        x = x - y;
	    } else {
	    	y = y - x;
	    }
	}
	return false;
}

Optimized iterative solution

> but still, the code isn't working. It's giving me memory limit
> exceeded error. Is there any other logic for this program?

On my Java your program with the fixes from the answer from Viral Lalakia crashes with a stack overflow if either input is 10 000 or more. The limit may be adjusted by adjusting the memory allocation for your JVM, but in practice you cannot increase memory to whatever you might like. The effective solution is to avoid recursion and code an iterative solution.

My key idea is to iterate backward from the destination (x, y). Viral Lalakia’s optimized solution also goes backward from the destination, which saves time, but as long as recursion is used, I suspect that it doesn’t save space, which is what the recursive program is running out of.

So in a loop find the previous coordinates from x and y.

• If x < y the previous coordinates must have been (x, y - x). So subtract x from y.
• If conversely x > y do the opposite subtraction.
• If x == y there are no possible previous coordinates. If we are at the starting point (1, 1), we know that a solution exists. Return true. If not, return false.

For each time through the loop check whether the number that you have decreased has become less than 1. If it has, there cannot be a solution. Return false.

BTW, the algorithm is the same as the algorithm for finding the greatest common divisor of x and y. So the very easy solution would be BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)) and compare the result to BigInteger.ONE to determine whether a path exists.

Link: Answer by Viral Lalakia containing an optimized recursive solution

Viral Lalakia has already pointed out the logical problems you had, however, the current approach wastes a lot of memory.

Explanation: You are using recursion, which is implicit usage of the stack, where your called methods and their status is stored. If x and y are VERY large numbers, then you will get a stack overflow issue (no pun intended!).

Solution

We know that

• initially you are on point (1, 1)
• your (a, b) position is either (1, 1), (a' + b, b) or (a, a + b')
• if a > b, then a = a' + b, so, the previous position is (a - b, b)
• if a < b, then b = a + b', so, the previous position is (a, b - a)
• if a == b, then you are either on the initial position of (1, 1), or, you cannot determine by the sheer values what was the previous state

This allows you to save a LOT of memory, assuming that you implement this iteratively. The ideas you need to comply to are as follows:

• if you have reached (x, y), then the algorithm ends, no matter what happened, as the question is whether it's solvable, you do not need to store the actual solution

• when you perform a step, you need to know whether you have added one of the coordinates to the other, or you have taken a step back

• if the point looks like (a, a), then you need to store what the previous value was in a stack, as well as the direction you have taken, so you can go back to it, positions of (a, a) must be treated in a special manner

• if you are NOT just after a backwards move, then try to increase the left coordinate first

• if you are just after a backwards move and before taking a backwards move, either a > b was true, or a == b was true with the condition that in the stack I have mentioned earlier the direction was in the left, then increment the second coordinate instead of the first one and change the direction of the top entry of the stack if it exists

• if you are just after a backwards move and either a < b was true, or a == b was true with the condition that in the stack the first coordinate is higher than the second, then the next move will be backwards as well

• if you perform a backwards move and the position before the backwards move was like (a, a), then you can remove the corresponding entry from your stack

• if, after a backward move you reach (1, 1), then you can end the algorithm, regardless of what the direction was, because having a step of (2, 1) is identical with having the step of (1, 2), including the subtrees, due to the commutative nature of adding

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