Mirror Reflection — Solution in Python, Java & C++
Mirror Reflection solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Mirror Reflection is a medium coding problem on math, number theory and geometry, asked in Amazon and Meta interviews.
- Difficulty: Medium
- Topics: Math, Number Theory, Geometry
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A square room has mirrors on all four walls and side length p. Three corners hold receptors: 0 at the south-east corner, 1 at the north-east corner and 2 at the north-west corner. The south-west corner has none.
A laser is fired from the south-west corner and first strikes the east wall at height q above receptor 0. It keeps reflecting off the walls until it hits a receptor.
Return the number of the receptor the ray reaches first. (It always reaches one.)
Example 1
Input: p = 2, q = 1
Output: 2
Explanation: The ray hits the east wall halfway up, bounces, and reaches the north-west corner.
Example 2
Input: p = 3, q = 1
Output: 1
Example 3
Input: p = 3, q = 2
Output: 0
Constraints
1 <= q <= p <= 1000
Hints for Mirror Reflection
Hint 1
Instead of reflecting the ray, reflect the room: stack mirrored copies of the square upwards, and the ray becomes a straight line rising
qper room width.Hint 2
The ray hits a corner when the height it has risen,
k*q, is a multiple ofp. Take the smallest suchk: thenk*q = m*pwithm = k*q / p.Hint 3
The parity of
ksays east or west wall, and the parity ofmsays top or bottom. Dividingpandqby 2 while both are even gives the same parities directly.
How to solve Mirror Reflection
Unfold the reflections: the ray travels in a straight line through mirrored copies of the room, and it meets a corner after the least k wall-widths with k*q a multiple of p. Only the parities of k and m = k*q/p matter.
Approach
- While
pandqare both even, halve both (this does not change where the ray goes). - If
pis now even (soqis odd), return 2. - If
qis even (sopis odd), return 0. - Otherwise both are odd: return 1.
Why it works
With g = gcd(p, q), the least k with p | k*q is k = p/g, and then m = q/g. Crossing an odd number of widths ends on the east wall and an even number on the west wall; rising an odd number of heights ends at the top and an even number at the bottom (in the unfolded picture each height flips the room). East-bottom is receptor 0, east-top 1, west-top 2; west-bottom is impossible because p/g and q/g cannot both be even. Halving p and q together until one is odd leaves p/g and q/g with the same parities, which is what the steps test.
Complexity
- Time —
O(log p) - Space —
O(1)
Pitfalls
- Simulating the bounces with floating-point geometry drifts; integers are enough.
- Forgetting to reduce by the common factor: p = 4, q = 2 behaves exactly like p = 2, q = 1.
- Receptor numbering is easy to swap: 0 is south-east, 1 north-east, 2 north-west.
Reference solution
Python
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 1Java
public static int mirrorReflection(int p, int q) {
while (p % 2 == 0 && q % 2 == 0) {
p /= 2;
q /= 2;
}
if (p % 2 == 0) return 2;
if (q % 2 == 0) return 0;
return 1;
}C++
int mirrorReflection(int p, int q) {
while (p % 2 == 0 && q % 2 == 0) {
p /= 2;
q /= 2;
}
if (p % 2 == 0) return 2;
if (q % 2 == 0) return 0;
return 1;
}JavaScript
var mirrorReflection = function(p, q) {
while (p % 2 === 0 && q % 2 === 0) {
p /= 2;
q /= 2;
}
if (p % 2 === 0) return 2;
if (q % 2 === 0) return 0;
return 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.