This a question that I got in a coding exam and couldn’t solve it at that time. The question states that,

You are currently at cell (1, 1) of an N X M grid. There is a rule that decides how you can move in the grid to reach the position (N, M). The rule is, that if you are at cell (x, y) then from there you can either move to cell (x, x+y) or to cell (x+y, y) in one step.

Your task is to find the minimum number of steps that you must take to reach cell (N, M) starting from current position i.e. (1, 1)

Note: If it is not possible to reach (N, M) from (1, 1), then return-1 as your output

Input Specification:

input1: An integer value representing the value of N where 1<=N input2: An integer value representing the value of M where M< 106

Output Specification:

Return the minimum number of steps.

Example 1:

input1: 3

input2: 2

Output: 2

Explanation:

(1, 1)-> (1, 2)-> (3, 2)

The number of steps involved are 2 only. Therefore, 2 will be returned as the output

Source: Windows Questions C++

## 3 thoughts on - Given two integers M & N, find minimum steps to reach M*N from (1,1), where condition of traversal is (x+y,y) or (x,y+x) and, x,y initially are (1,1) [closed]

Need and answer for the above question

#include

using namespace std;

int main(){

int N,M;

cin>>N>>M;

queue<pair>q;

pairtarget={N,M};

int count=0;

int ans=-1;

q.push({1,1});

while(!q.empty()){

int sz=q.size();

for(int i=0;i<sz;i++){

auto cur=q.front();

cout<<"{ "<<cur.first<<" "<<cur.second<<" } ";

q.pop();

if(cur==target){

ans=count;

break;

}

if(cur.first+cur.second<=N )q.push({cur.first+cur.second, cur.second});

if(cur.first+cur.second<=M)q.push({cur.first,cur.first+cur.second});

}

cout<<endl;

if(ans!=-1)break;

count++;

}

cout<<ans<<endl;

}

Send this code