Mirror Reflection: Unfolding a Laser Beam with GCD

Mirror Reflection is LeetCode 858. You have a special square room with mirrors on all four walls. The room has side length p. Three of the four corners have receptors: receptor 0 at the southeast (bottom-right), receptor 1 at the northeast (top-right), and receptor 2 at the northwest (top-left). The southwest corner has no receptor. A laser ray shoots from the southwest corner and first meets the east wall at a distance q from receptor 0. Return the number of the receptor the ray eventually hits.

A few examples:

• p = 2, q = 1 returns 2 (the ray bounces once and hits the northwest corner)
• p = 3, q = 1 returns 1 (the ray bounces twice and hits the northeast corner)

The constraints guarantee that 1 <= q <= p <= 1000 and the ray will always reach a receptor.

The problem

Picture a square room where every wall is a perfect mirror. A laser shoots from the bottom-left corner toward the right wall, hitting it at height q. From there it bounces. Then it bounces again. And again. Eventually it lands on one of the three receptor corners. Your job is to figure out which one.

Simulating the bounce (brute force idea)

You could try to simulate each bounce: track the ray position on the wall, figure out the angle of reflection, compute where it hits the next wall, and repeat. This works in principle, but it has two problems. First, it is fiddly to implement. You need to track direction and position carefully, and floating-point errors can accumulate. Second, for large p and small q, the number of bounces can be very large.

There is a much cleaner approach that avoids simulation entirely.

The key insight: unfold the room

Instead of bouncing the laser inside a single room, imagine "unfolding" the reflections. Every time the ray would bounce off a wall, you place a mirrored copy of the room on the other side of that wall and let the ray continue in a straight line.

Think of it this way: stacking rooms vertically, alternating between the original and its mirror image. The zigzagging laser inside the real room becomes a straight diagonal line cutting through the stack of rooms. The question "which receptor does the ray hit?" becomes "which corner of which stacked room does the straight line reach first?"

The straight line reaches a corner when the total vertical distance traveled is a multiple of p (so the ray is at the top or bottom of a room) and the total horizontal distance is a multiple of p (so the ray is at the left or right edge of a room). Since the ray rises q for every p it travels horizontally, the first time both conditions are met simultaneously is at total vertical height LCM(p, q).

Step-by-step walkthrough

The code

Once you understand the unfolding trick, the code becomes very short. Divide both p and q by their GCD to reduce them to their simplest form, then check which one is even.

from math import gcd

def mirrorReflection(p: int, q: int) -> int:
    g = gcd(p, q)
    p //= g
    q //= g

    # After dividing by GCD, p and q are coprime.
    # They cannot both be even.
    if p % 2 == 0:
        return 2
    if q % 2 == 0:
        return 0
    return 1

You can also write this with a while loop that divides out all common factors of 2, but the GCD approach is cleaner and equivalent.

def mirrorReflection(p: int, q: int) -> int:
    while p % 2 == 0 and q % 2 == 0:
        p //= 2
        q //= 2

    if p % 2 == 0:
        return 2
    if q % 2 == 0:
        return 0
    return 1

Both solutions produce the same result. The first one is more direct because gcd strips all common factors at once (not just factors of 2), but since p and q are coprime after dividing by GCD, only one of them can be even.

Why this works

The math behind this solution ties together a few number theory ideas.

LCM determines the meeting point. In the unfolded room, the laser travels in a straight line with slope q / p. It hits a corner when the vertical distance is a multiple of p and the horizontal distance is a multiple of q. The smallest such distance is LCM(p, q) = p * q / GCD(p, q).

Room counts reveal the corner. At height LCM(p, q), the number of horizontal bounces is LCM(p, q) / q = p / GCD(p, q), and the number of vertical room heights stacked is LCM(p, q) / p = q / GCD(p, q). Call these p' and q' (p and q divided by their GCD).

Parity maps to receptors. An even number of horizontal bounces means the ray ends on the same side it started (left), while an odd number means it ends on the opposite side (right). Similarly for vertical: an even number of room-heights means the ray is at the bottom, and odd means the top.

• p' even, q' odd: the ray is on the left side and at the top. That is the northwest corner, receptor 2.
• p' odd, q' even: the ray is on the right side and at the bottom. That is the southeast corner, receptor 0.
• p' odd, q' odd: the ray is on the right side and at the top. That is the northeast corner, receptor 1.

Since p' and q' are coprime (we divided out the GCD), they cannot both be even. That covers all cases.

Complexity analysis

The building blocks

This problem showcases two reusable patterns that appear across many math problems.

GCD / LCM reduction

When a problem involves two quantities that interact periodically, dividing by GCD often reveals the essential structure. You saw the same idea in problems like computing least common multiples for scheduling, fraction simplification, and cycle detection in number theory. The pattern is: find the GCD, divide it out, and work with the coprime result.

from math import gcd
g = gcd(a, b)
a_reduced = a // g
b_reduced = b // g
# Now a_reduced and b_reduced are coprime

Even/odd parity analysis

After reducing to the simplest form, the answer depends entirely on whether each value is even or odd. Parity checks show up in many places: determining if a permutation is reachable, checking if a game position is winning or losing, and deciding which side of a grid you end up on after some number of steps.

if x % 2 == 0:
    # even case
else:
    # odd case

The combination of GCD reduction and parity checking turns what looks like a geometry simulation into a three-line decision.

Edge cases

q equals p. The laser goes straight up from the southwest corner and hits the northwest corner immediately. GCD(p, p) = p, so p' = 1 (odd) and q' = 1 (odd). Return 1? Wait: if q = p, the ray hits the east wall at height p, which is the top-right corner, receptor 1. And indeed, both odd returns 1. Correct.

q equals 1. The ray barely rises. It takes many bounces to reach a receptor. GCD(p, 1) = 1, so p' = p and q' = 1 (odd). If p is odd, return 1. If p is even, return 2.

p and q share a large common factor. For example, p = 100, q = 60. GCD = 20, so p' = 5 (odd), q' = 3 (odd). Return 1. The GCD division collapses the problem down to a small coprime pair.

From understanding to recall

The unfolding trick is the conceptual leap. Once you see that bouncing inside a mirror room is equivalent to walking in a straight line through tiled copies of the room, the rest follows from basic number theory. The GCD gives you the first receptor hit, and parity tells you which receptor it is.

Two things to internalize: first, the unfolding visualization (replace bounces with room copies). Second, the three-case parity table (both odd is receptor 1, p even is receptor 2, q even is receptor 0). If you can recall the table, the code writes itself.

Practice reconstructing the solution from the table alone. Given p and q, compute p' = p / gcd(p,q) and q' = q / gcd(p,q), then check parity. That sequence takes under 30 seconds to write once it is in muscle memory.

Related posts

• Pow(x, n) - Another math problem where a clever reduction (exponentiation by squaring) replaces brute force iteration with logarithmic work.
• Sqrt(x) - Uses binary search on integers, another case where the right mathematical framing avoids the need for simulation.
• Divide Two Integers - Bit shifting to avoid multiplication, similar in spirit to using GCD to avoid bounce simulation.