Watch 10 video solutions for Mirror Reflection, a medium level problem involving Math, Geometry, Number Theory. This walkthrough by Algorithms Made Easy has 9,691 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000Problem Overview: A laser starts from the southwest corner of a square room with mirrors on every wall. The beam travels toward the east wall and reflects perfectly. Given the room side length p and the vertical offset q, determine which receptor (0, 1, or 2) the beam hits first.
Approach 1: Iterative Simulation (O(p) time, O(1) space)
This method simulates the laser reflections step by step. Each time the beam reaches a vertical wall, it reflects and continues toward the opposite wall while maintaining the same slope. You track the vertical position after each horizontal traversal and flip direction whenever the beam hits the top or bottom boundary. The simulation stops once the beam lands exactly on one of the receptor corners. This approach mirrors the physical process and helps build intuition about the reflections, but it can require up to O(p) steps when p is large.
Approach 2: Mathematical Approach Using GCD (O(log n) time, O(1) space)
The key observation is that repeated reflections are equivalent to extending the room into mirrored copies and letting the beam travel in a straight line. The beam reaches a receptor when the vertical travel equals a multiple of p. This reduces the problem to finding the least common multiple of p and q. Compute lcm = p * q / gcd(p, q). The number of room extensions horizontally is lcm / p and vertically is lcm / q. Their parity determines the receptor: even horizontal extensions lead to receptor 2, odd horizontal with odd vertical leads to receptor 1, and odd horizontal with even vertical leads to receptor 0. The gcd computation makes the solution efficient and is a classic trick in number theory problems involving repeating patterns.
This reasoning converts a geometric reflection problem into pure arithmetic. Instead of simulating every bounce, you analyze how many room copies the beam effectively crosses. Concepts from math and geometry combine here: geometry explains the reflections, while number theory determines when the beam aligns with a receptor.
Recommended for interviews: The mathematical GCD approach is what interviewers expect. It demonstrates pattern recognition and the ability to convert geometry into arithmetic reasoning. The simulation approach shows understanding of the physical behavior, but the optimized math solution proves you can identify the hidden number theory insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(p) | O(1) | Useful for understanding the reflection mechanics or when constraints are small |
| Mathematical Approach Using GCD | O(log n) | O(1) | Optimal solution for large inputs; preferred in interviews and competitive programming |