Mirror Reflection - Solution & Explanation
Problem Statement
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 <= 1000
Approach Overview
Problem 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 1: Mathematical Approach Using GCD
This approach leverages the properties of the greatest common divisor (GCD). The ray will hit a receptor the first time it reaches a location where both the vertical and horizontal distances are multiples of the given dimensions of the square room.
Specifically, the ray's first encounter with a receptor will happen after k*step_x = multiple of p and k*step_y = multiple of q. The reflections allow us to simplify the problem into smaller parts which can be resolved by finding the lowest common multiple of the grid dimension.
The solution calculates the greatest common divisor (GCD) of p and q to simplify the problem. Depending on the parity of the reduced p and q, it determines which receptor will be hit first by the ray.
Complexity
Time Complexity: O(log(min(p, q))) due to the GCD calculation.
Space Complexity: O(1) since no additional space is used.
Approach 2: Iterative Simulation
This approach simulates the path of the light by extending the room along a grid infinitely. Each step checks whether the conditions for meeting a receptor are fulfilled. Although less efficient due to direct simulation, it provides a straightforward illustration of the problem dynamics.
This Python solution directly simulates the trajectory of the laser. The loop continues to increment the variables until the room's dimensions align, consistently checking whether the ray has reached a receptor or not.
Complexity
Time Complexity: O(p / gcd(p, q))
Space Complexity: O(1).
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Mathematical Approach Using GCD | Time Complexity: O(log(min(p, q))) due to the GCD calculation. |
| Iterative Simulation | Time Complexity: O(p / gcd(p, q)) |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Mirror Reflection | Live Coding with Explanation | Leetcode - 858 • Algorithms Made Easy • 9,787 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Mirror Reflection easy or hard?
Mirror Reflection Python/Java solution
How to solve Mirror Reflection in O(log n)?
What is the best approach for Mirror Reflection?
Is Mirror Reflection asked at Google/Amazon/Meta?
What data structure is used in Mirror Reflection?
What is the time complexity of Mirror Reflection?
Ready to solve this problem?
Practice Mirror Reflection with our built-in code editor and test cases.
Practice on FleetCode