Reflection

Easy
0/40
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in company
Amazon

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 1
3 2
Sample Output 1:
3
1
Explanation for Sample Input 1:
In test case 1:
X=2 and Y=1
Following is how reflection takes place.


In test case 2:
X=3 and Y=2
Following is how reflection takes place.

Sample Input 2:
3
26 7
15 6
Sample Output 2:
3
1
Explanation for Sample Input 2:
For first test case, 3 reflections takes place.
For second test case, 1 reflection takes place.
Hint

Model the ray such that it always travels in a straight line.

Approaches (1)
Mathematical 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:

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

O( Y ),  where Y is the height at which the laser touches the mirror at first.

 

In the worst case, in while loop ‘a’ will go up to ‘Y’ thus complexity O(Y).

Space Complexity

O(1) 

 

No additional memory will be used except for the reserved stack memory.

Code Solution
(100% EXP penalty)
Reflection
Full screen
Console