Mirror Reflection
Problem
A square room has mirrors on all four walls. Three receptors are at corners 0, 1, and 2 (every corner except the southwest). The room has side length p and a laser fires from the southwest corner, first striking the east wall at distance q from receptor 0. Return which receptor the ray hits first.
p = 2, q = 12from math import gcd
def mirror_reflection(p, q):
g = gcd(p, q)
p, q = (p // g) % 2, (q // g) % 2
if p and q:
return 1
return 0 if p else 2function mirrorReflection(p, q) {
const gcd = (a, b) => b ? gcd(b, a % b) : a;
const g = gcd(p, q);
p = (p / g) % 2;
q = (q / g) % 2;
if (p && q) return 1;
return p ? 0 : 2;
}class Solution {
public int mirrorReflection(int p, int q) {
int g = gcd(p, q);
p = (p / g) % 2;
q = (q / g) % 2;
if (p == 1 && q == 1) return 1;
return p == 1 ? 0 : 2;
}
private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}int mirrorReflection(int p, int q) {
int g = __gcd(p, q);
p = (p / g) % 2;
q = (q / g) % 2;
if (p && q) return 1;
return p ? 0 : 2;
}Explanation
Instead of bouncing the laser around a mirrored room, the clever trick is to unfold the reflections into a straight line. The ray travels straight and lands at a corner once the total horizontal distance is a multiple of p and the total vertical distance is also a multiple of p.
That first shared multiple is the least common multiple of p and q. Dividing through by their gcd shrinks the room to its essential shape without changing which corner is hit, so we reduce p and q by g = gcd(p, q).
After reduction, only the parities (odd/even) of p and q matter. The code computes p % 2 and q % 2 and reads off the answer: both odd gives receptor 1, p odd (q even) gives 0, and p even gives 2.
This works because each parity tells you whether the unfolded ray ends on the top or bottom wall and the left or right wall, which together pin down the exact corner.
Example: p = 2, q = 1. The gcd is 1, so reduced p % 2 = 0 and q % 2 = 1. Since p is even, the answer is receptor 2.