Help me with this problem

Harsh just loves numbers and loves to have fun with them . Apparently he has two numbers with him , say X and Y . Both of them are integers . Now from these numbers he wants another number , say L . But he doesn’t know how to derive it and needs your help . Given the two numbers you can add one to another , and you can do this any number of times . For example, you can add X to Y , or Y to X , and this can be done until any combination makes either X equal to L or Y equal to L .

“Well , this might actually lead to a solution”, said Harsh, ”but can you do it in a minimum number of operations ?”.
Output Format:

For each test case, output the required minimum number of operations .

Constraints:

1<= T <=20
1<= L <=1000000

Just to make this problem a little simple let’s assume both the values of X and Y is 1 .
please suggest me some approach for this . Also , if X ,Y are not 1 , then how will this problem be    solved?

This might not be the most efficient solution, but something which i came up with initially.

So basically you use BFS and the answer you find will be the shortest path.

Let me define a node as having:X,Y and Path

node 1: 1,1,0
Push node 1 into queue.
While(q.count>0)
{node=dequeue()
if(node.X+node.Y==L)
return node.path+1
else
{
enqueue(node.X+node.Y,node.Y,node.path+1);
enqueue(node.X,node.Y+node.X,node.path+1);
}
}

What do you think?

@varun_2367 , please explain the condition “q.count>0” in while loop ?
when i will push the first node into the queue , q.count will be zero , then how will it proceed further…?

When you add node 1, then count will become 1.
Empty queue will have zero count.

-1 Please don’t post questions from an ongoing contest,even if they are not from Codechef.

1 Like
//