Last Updated: 15 Apr, 2021

Reflection

Easy

Asked in company

Solve now

Problem statement

You are given a square mirror of length ‘X’, and you have receptors in mirrors on corners 1, 2, 3. You set off a laser from corner 0 towards the right side ( side with corner 1 and 2) of the mirror which meets the mirror at height of ‘Y’. You have to return the receptor number, which the laser touches first.

Note: The laser will touch the receptors eventually.

Input Format:

The first line of the input contains ‘T’ denoting the number of test cases.

In the first line of each test case take two space-separated integers,  ‘X’ and ‘Y’

Output Format:

For each test case, print the receptor number which the laser touches first.

Note:

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
0 <= X,Y <= 5000

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Explanation:

First, we will reduce ‘X’ and ‘Y’ by their common factors because that won’t impact our final outcome. i.e. the result of pair k*X and k*Y will be the same as the result of pair ‘X’ and ‘Y’. This is because k*X and k*Y can be just seen as a zoomed-up version of the other pair.

We can assume that the laser never gets reflected rather it travels in a straight line and we just invert the mirror to find the corner it reaches.

Eg:

Image 1:

Image 2:

The figure below shows the reflection of the mirror horizontally and vertically. Every cell in the following table tells the top right corner number of the mirror which would be at that place.

Image 3:

If we somehow got the number of horizontal and vertical flips of the mirror then we can find the receptor the laser hit as it will hit the top right corner ( if we move in a straight line only).

From image 2, we can see that at height 2*X, the height is also equal to 3*Y

Thus 2*X= 3*Y or (number of vertical flips)*X = (number of horizontal flips)*Y

Let’s say, ‘a’= number of vertical flips and ‘b’= number of horizontal flips

Then to hit a corner a*X= b*Y, where ‘a’ and ‘b’ are integers. Then we can just solve for the smallest a and b that satisfies this equation.

Algorithm:

Create a variable ‘a’ = 1 and ‘b’ = 1.
While (X * a) % Y != 0:
- Increment a.
Set b = (X * a) / Y.
We got our ‘a’ and ‘b’.
Now if ‘a’ is odd and ‘b’ is odd return 2, else if ‘b’ is even return 3.
If ‘a’ is even then return 1 (we can’t reach corner 3 so there is no point in comparison for it).

Solve now