LeetCode Problem 858

Difficulty: 🟡 Medium
Topics: Math, Geometry, Number Theory

Solution

LeetCode 858 - Mirror Reflection

Problem Understanding

This problem describes a square room with perfectly reflective walls. The room has side length p, and there are three receptors placed at three corners of the square:

• Receptor 0 is at the southeast corner
• Receptor 1 is at the northeast corner
• Receptor 2 is at the northwest corner

The laser starts from the southwest corner and travels diagonally toward the east wall. It first hits the east wall at a vertical distance q from receptor 0.

The goal is to determine which receptor the laser hits first after repeatedly reflecting off the walls.

The important detail is that reflections behave exactly like geometric mirror reflections. Instead of simulating each bounce individually, we can think of the room as being repeated infinitely in a tiled pattern. In this expanded view, the laser travels in a straight line through repeated mirrored rooms. The first time this straight line reaches a corner corresponds to the first receptor hit in the original room.

The input consists of two integers:

• p, the side length of the room
• q, the vertical displacement when the laser first reaches the east wall

The output is a single integer representing the receptor number.

The constraints are small:

• 1 <= q <= p <= 1000

Even though the limits are not large, the geometry can create many reflections if simulated directly. A naive simulation can become messy and error-prone because floating point precision and repeated reflections introduce unnecessary complexity.

Several edge cases are important:

• When q == p, the laser goes directly to the northeast corner, which is receptor 1
• When q evenly divides p, the pattern may terminate quickly
• When p and q share a common divisor, reducing the ratio is essential
• The parity of the number of room extensions determines the receptor

The problem guarantees that the laser eventually reaches a receptor, so we never need to handle infinite loops or impossible cases.

Approaches

Brute Force Simulation

A direct approach is to simulate the laser's movement and reflections. We could track:

• The current position
• The current direction
• Which wall is hit next
• How the direction changes after reflection

Eventually, the laser reaches one of the receptors.

This approach is conceptually straightforward because it mirrors the physical process. However, it introduces several complications:

• Floating point arithmetic may cause precision issues
• Reflection logic becomes cumbersome
• Determining exact corner hits is tricky
• Many reflections may occur before termination

Although the constraints are small, the implementation complexity is unnecessarily high.

Optimal Mathematical Observation

The key insight is that reflections can be eliminated by unfolding the room.

Instead of reflecting the laser, imagine reflecting the room itself every time the laser hits a wall. In this expanded infinite grid of rooms, the laser travels in a perfectly straight line.

The laser reaches a receptor when both conditions are true simultaneously:

• Horizontally, it has traveled an integer multiple of p
• Vertically, it has also aligned with a room boundary

Mathematically, we seek the smallest positive integer L such that:

$$L = k \cdot p = m \cdot q$$

This means L must be the least common multiple of p and q.

Once we find:

$$\text{LCM}(p, q)$$

we determine:

• m = LCM / q
• n = LCM / p

The parity of these values determines the receptor:

• n odd and m odd → receptor 1
• n odd and m even → receptor 0
• n even and m odd → receptor 2

A cleaner implementation avoids explicitly computing the LCM. We repeatedly divide both p and q by 2 while both are even. Then:

• p odd and q odd → receptor 1
• p odd and q even → receptor 0
• p even and q odd → receptor 2

This works because only parity matters after removing common factors of 2.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k)	O(1)	Simulates reflections one by one
Optimal	O(log(min(p, q)))	O(1)	Uses number theory and parity analysis

Algorithm Walkthrough

Optimal Algorithm

1. Repeatedly divide both p and q by 2 while they are both even.

This removes all shared powers of two. Only the parity of the remaining values matters for determining the receptor. 2. After reduction, examine whether p and q are odd or even.

There are only three valid cases:

• If p is odd and q is odd, return 1
• If p is odd and q is even, return 0
• If p is even and q is odd, return 2

3. Return the corresponding receptor number.

Why it works

The laser reaches a receptor when the vertical and horizontal distances align at a corner. This occurs at the least common multiple of p and q.

After removing shared factors of two, only parity determines which side and which corner the laser reaches:

• Odd horizontal extensions mean the laser ends on the east wall
• Even horizontal extensions mean it ends on the west wall
• Odd vertical extensions mean it ends on the top wall

Combining these parity conditions uniquely identifies the receptor.

Python Solution

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

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

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

        return 2

The implementation begins by removing all common factors of two from p and q. This normalization step is important because the final receptor depends only on whether the reduced values are odd or even.

The first while loop performs this reduction efficiently using integer division.

After reduction, the code checks the parity combinations:

• Both odd corresponds to receptor 1
• p odd and q even corresponds to receptor 0
• The remaining valid case is receptor 2

The logic is compact because the mathematical structure reduces the problem to simple parity analysis.

Go Solution

func mirrorReflection(p int, q int) int {
    for p%2 == 0 && q%2 == 0 {
        p /= 2
        q /= 2
    }

    if p%2 == 1 && q%2 == 1 {
        return 1
    }

    if p%2 == 1 && q%2 == 0 {
        return 0
    }

    return 2
}

The Go implementation follows exactly the same mathematical reasoning as the Python version.

Because all operations involve small integers, there are no integer overflow concerns. Go integer division naturally truncates toward zero, which matches the intended behavior for repeatedly dividing by two.

No additional data structures are needed, so the implementation remains concise and efficient.

Worked Examples

Example 1

Input:

p = 2, q = 1

Initial values:

Step	p	q
Start	2	1

The loop condition requires both values to be even.

• p is even
• q is odd

So the loop stops immediately.

Parity analysis:

• p is even
• q is odd

This corresponds to receptor 2.

Output:

2

Example 2

Input:

p = 3, q = 1

Initial values:

Step	p	q
Start	3	1

Neither value is even, so the reduction loop does nothing.

Parity analysis:

• p is odd
• q is odd

This corresponds to receptor 1.

Output:

1

Additional Example

Input:

p = 4, q = 2

Reduction steps:

Step	p	q
Start	4	2
Divide by 2	2	1

Now:

• p is even
• q is odd

This corresponds to receptor 2.

Output:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log(min(p, q)))	Repeatedly divides by 2
Space	O(1)	Uses constant extra memory

The loop removes common powers of two from both numbers. Since each iteration halves the values, the number of iterations is logarithmic in the smaller input value.

No auxiliary data structures are allocated, so the space usage remains constant.

Test Cases

sol = Solution()

assert sol.mirrorReflection(2, 1) == 2  # Example 1
assert sol.mirrorReflection(3, 1) == 1  # Example 2
assert sol.mirrorReflection(4, 2) == 2  # Common factor reduction
assert sol.mirrorReflection(5, 5) == 1  # Direct hit to northeast corner
assert sol.mirrorReflection(6, 4) == 0  # Reduced to odd-even case
assert sol.mirrorReflection(10, 5) == 2  # Reduced to even-odd case
assert sol.mirrorReflection(1, 1) == 1  # Smallest valid input
assert sol.mirrorReflection(1000, 500) == 2  # Large even values
assert sol.mirrorReflection(999, 333) == 1  # Large odd values
assert sol.mirrorReflection(8, 6) == 0  # Multiple reductions

Test	Why
p=2, q=1	Validates receptor 2 case
p=3, q=1	Validates receptor 1 case
p=4, q=2	Tests reduction by powers of two
p=5, q=5	Tests direct diagonal to receptor 1
p=6, q=4	Tests odd-even parity result
p=10, q=5	Tests even-odd parity result
p=1, q=1	Smallest valid input
p=1000, q=500	Large even-number reduction
p=999, q=333	Large odd-number scenario
p=8, q=6	Multiple division reductions

Edge Cases

Case 1: q == p

When q equals p, the laser travels directly toward the northeast corner without requiring any reflections. This corresponds to receptor 1.

A buggy implementation might incorrectly simulate unnecessary reflections or mishandle the direct diagonal path. The parity-based approach handles this naturally because both reduced values become odd.

Case 2: Large Shared Powers of Two

Inputs like p = 128 and q = 64 contain many common factors of two. If the implementation does not reduce these factors correctly, the parity logic becomes incorrect.

The solution explicitly removes all shared powers of two before checking parity, ensuring correctness regardless of how many reductions are needed.

Case 3: One Value Odd, One Even

Cases where one value is odd and the other even are especially important because they determine whether the laser ends on the east wall or west wall.

For example:

p = 6, q = 4

After reduction:

p = 3, q = 2

This maps to receptor 0.

Incorrect implementations often confuse receptors 0 and 2 because they do not correctly interpret parity after normalization. The explicit parity checks in this implementation avoid that mistake entirely.