Mirror Reflection

Problem Description

There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 0, 1, and 2. The square room has walls of length p and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor. Given the two integers p and q, return the number of the receptor that the ray meets first.

Key Insights

• The ray reflects off the walls based on its trajectory, and the position of the receptors determines where the ray will meet first.
• The ray will reach the east wall after traveling a distance q, and then it will reflect according to the angle of incidence.
• The problem can be understood through the concept of the Least Common Multiple (LCM) of the dimensions involved.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To determine which receptor the ray meets first, we can utilize the relationship between the distances traveled by the ray. The ray will first hit a wall and then reflect. The effective distance the ray travels vertically (up or down) is influenced by the ratio of q to p. By calculating the LCM of p and q, we can determine how many times the ray reflects off the walls before reaching a receptor.

1. Calculate the number of vertical bounces the ray makes by evaluating q/p.
2. The receptor the ray meets will depend on whether the number of bounces is odd or even:
   • If it reaches the top (1) when bouncing vertically, the ray meets receptor 1.
   • If it reaches the bottom (2) when bouncing vertically, the ray meets receptor 2.
   • If it completes without hitting either (0), it meets receptor 0.

Code Solutions