# LeetCode 858: Mirror Reflection

## Problem Restatement

We have a square room with mirrored walls.

The side length of the room is `p`.

A laser starts from the southwest corner. It first hits the east wall at a distance `q` from receptor `0`.

There are three receptors:

| Receptor | Corner |
|---|---|
| `0` | Southeast corner |
| `1` | Northeast corner |
| `2` | Northwest corner |

The southwest corner has no receptor.

The laser reflects from the mirrors until it reaches one of the receptors.

Return the receptor number that the laser reaches first.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `p`, the side length of the square room |
| Input | `q`, the height where the laser first hits the east wall |
| Output | The receptor number: `0`, `1`, or `2` |
| Constraint | `1 <= q <= p <= 1000` |
| Guarantee | The laser eventually reaches a receptor |

Function shape:

```python
class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        ...
```

## Examples

Example 1:

```python
p = 2
q = 1
```

The room has side length `2`.

The laser first reaches the east wall at height `1`.

After reflecting, it eventually reaches the northwest corner.

So the answer is:

```python
2
```

Example 2:

```python
p = 3
q = 1
```

The laser reaches the northeast corner.

So the answer is:

```python
1
```

## First Thought: Simulate the Reflection

One direct idea is to simulate the ray.

Track:

1. Current position
2. Current direction
3. Which wall the ray hits next
4. How the direction changes after reflection

This is possible, but it is unnecessarily complicated.

The ray can bounce many times. Handling floating-point positions and mirror direction changes also makes the implementation more error-prone.

A cleaner approach is to avoid reflection entirely.

## Key Insight

Instead of reflecting the laser, reflect the room.

When the laser hits a wall, imagine that it continues straight into a mirrored copy of the room.

So the laser travels in a straight line across repeated square rooms.

The ray first hits the east wall at height `q`, so for every horizontal distance `p`, the vertical height increases by `q`.

We need the first time the laser reaches a corner.

That happens when the vertical distance traveled is a multiple of `p`.

So we need the smallest positive distance that is a multiple of both `p` and `q`.

That value is:

```python
lcm(p, q)
```

Let:

```python
vertical_rooms = lcm(p, q) // p
horizontal_rooms = lcm(p, q) // q
```

These values tell us which repeated room contains the receptor.

Only their parity matters.

| `horizontal_rooms` | `vertical_rooms` | Receptor |
|---|---|---|
| odd | odd | `1` |
| odd | even | `0` |
| even | odd | `2` |

The case where both are even cannot be the first receptor hit, because then we could divide both by `2` and find an earlier corner.

## Algorithm

Compute:

```python
g = gcd(p, q)
```

Then reduce:

```python
p_reduced = p // g
q_reduced = q // g
```

These reduced values carry the same parity information as the LCM room counts.

Now decide by parity:

1. If `p_reduced` is even, return `2`.
2. Else if `q_reduced` is even, return `0`.
3. Otherwise, return `1`.

This corresponds to:

| Reduced `p` | Reduced `q` | Result |
|---|---|---|
| even | odd | `2` |
| odd | even | `0` |
| odd | odd | `1` |

## Correctness

In the unfolded-room view, the laser travels in a straight line instead of reflecting.

The laser reaches a receptor exactly when it reaches a corner of some copied room. A copied room corner occurs when both the horizontal and vertical distances align with multiples of `p`.

The vertical distance grows by `q` for every horizontal room width `p`, so the first corner hit occurs at the least common multiple of `p` and `q`.

After dividing by `gcd(p, q)`, the remaining parity tells us whether the final corner is on the left or right side, and whether it is on the top or bottom side.

If reduced `p` is even and reduced `q` is odd, the ray ends on the left top corner, which is receptor `2`.

If reduced `p` is odd and reduced `q` is even, the ray ends on the right bottom corner, which is receptor `0`.

If both are odd, the ray ends on the right top corner, which is receptor `1`.

These are all possible first-hit cases, so the algorithm returns the correct receptor.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log min(p, q))` | Computing `gcd` uses Euclid's algorithm |
| Space | `O(1)` | Only a few integers are stored |

## Implementation

```python
from math import gcd

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        g = gcd(p, q)

        p //= g
        q //= g

        if p % 2 == 0:
            return 2

        if q % 2 == 0:
            return 0

        return 1
```

## Code Explanation

First, compute the greatest common divisor:

```python
g = gcd(p, q)
```

Then reduce both numbers:

```python
p //= g
q //= g
```

This removes the shared scale. We only care whether the reduced values are odd or even.

If reduced `p` is even:

```python
if p % 2 == 0:
    return 2
```

the laser reaches receptor `2`.

If reduced `q` is even:

```python
if q % 2 == 0:
    return 0
```

the laser reaches receptor `0`.

Otherwise both reduced values are odd:

```python
return 1
```

so the laser reaches receptor `1`.

## Testing

```python
def test_mirror_reflection():
    s = Solution()

    assert s.mirrorReflection(2, 1) == 2
    assert s.mirrorReflection(3, 1) == 1
    assert s.mirrorReflection(4, 3) == 2
    assert s.mirrorReflection(5, 2) == 0
    assert s.mirrorReflection(6, 4) == 0
    assert s.mirrorReflection(6, 3) == 2

    print("all tests passed")

test_mirror_reflection()
```

Test meaning:

| Test | Why |
|---|---|
| `p = 2`, `q = 1` | Standard example, reaches receptor `2` |
| `p = 3`, `q = 1` | Standard example, reaches receptor `1` |
| `p = 4`, `q = 3` | Reduced `p` even, receptor `2` |
| `p = 5`, `q = 2` | Reduced `q` even, receptor `0` |
| `p = 6`, `q = 4` | Reduction changes parity |
| `p = 6`, `q = 3` | Shared factor leaves reduced `p` even |