Is It Possible – Interview question

No Comments

Question:

You are given a pair of integers (x,y). You may perform either of the two operations below,in any order, zero or more times.

1. (x,y) -> (x+y,y)
2. (x,y) -> (x,y+x)

For example, you can start with (1, 4), change it to (5, 4), change that to (5, 9), and then change that again to (5, 14).
You are given four integers: a, b, c, and d. Return “Yes” (without quotes) if it is possible to start with the pair (a, b) and end with the pair (c, d). Otherwise, return “No”.

Method signature: String isPossible(int a, int b, int c, int d)

Input
Four integers in separate lines.

Output
One string “Yes” or “No”.

Constraints

1≤ a,b,c,d ≤ 1000

Sample Input
1
4
5
9

Sample Output
Yes

Explanation
(1, 4) -> (5, 4) -> (5, 9) .


Answer:

I’m using Breadth-First-Search (BFS) here. Start with the node(a,b) and consider all possible nodes reachable from it. Starting from (a,b) we can reach to (a+b,b) and (a, a+b). Again from (a+b,b) we can reach to (a+2b, b) and (a+b, a+2b) and so on. There’s a queue storing these nodes. If the front of queue matches the pair(c,d) it returns “YES” else “NO”.

#include <iostream>
#include <queue>

using namespace std;

string isPossible (int, int, int, int);

int main (){

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << isPossible (a, b, c, d) << endl;

    return 0;
}


string isPossible (int a, int b, int c, int d){
    
        queue < pair<int, int> > q;

        q.push(make_pair(a,b));
        bool flag =  false;

        while ( !q.empty() ){
            pair<int, int> topElem = q.front();

            int firstVal = q.front().first;
            int secondVal = q.front().second;

            if (firstVal == c && secondVal == d){
                flag = true;
                break;
            }

            if (firstVal <= c && secondVal <=d){

                q.push (make_pair(firstVal + secondVal, secondVal) );
                q.push (make_pair(firstVal, firstVal + secondVal) );
            }

            q.pop();
        }

        if (flag)
            return "YES";
        
    return "NO";
}

This code might not be covering all the scenarios but will serve the purpose of a good start. Any suggestions and comments are welcome.

Categories: Algorithm, Data structure