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.
The test cases are guaranteed so that the ray will meet a receptor eventually.
Example 1:
Input: p = 2, q = 1 Output: 2 Explanation: The ray meets receptor 2 the first time it gets reflected back to the left wall.
Example 2:
Input: p = 3, q = 1 Output: 1
Constraints:
1 <= q <= p <= 1000The Mirror Reflection problem can be solved by modeling how a laser beam reflects inside a square room with mirrored walls. Instead of simulating every reflection, a more efficient insight is to imagine the room being repeatedly extended vertically and horizontally until the laser reaches a receptor directly.
The key idea is to determine when the beam simultaneously reaches a vertical boundary and the top edge. This occurs when the beam travels a distance equal to the least common multiple of the room size p and the vertical offset q. By reducing p and q using their greatest common divisor, we can analyze the parity (odd/even) of the resulting values to determine which receptor the beam hits.
This mathematical approach avoids geometric simulation and leads to a constant-time reasoning process after computing the GCD. The method relies on number theory properties and parity checks, making it both elegant and efficient for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| GCD Reduction & Parity Check | O(log(min(p,q))) | O(1) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Mirror Reflection is a common medium-level interview problem that tests mathematical reasoning and optimization. It often appears in coding platforms and interviews to evaluate how candidates replace brute-force simulation with mathematical insight.
The optimal approach uses number theory. By computing the greatest common divisor (GCD) of p and q and reducing the values, you can analyze whether the resulting values are odd or even to determine which receptor the laser reaches. This avoids simulating reflections and gives a very efficient solution.
No special data structures are required. The solution mainly relies on mathematical operations such as computing the GCD and checking parity, making it a pure math and number theory problem.
LCM helps determine when the horizontal and vertical movements of the laser align at a corner or receptor. Using the GCD simplifies the calculation by reducing p and q, allowing you to check parity and identify the correct receptor mathematically.