# Mirror Reflection
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/mirror-reflection)
Canonical: https://scaleengineer.com/dsa/problems/mirror-reflection
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
---
## Problem
There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered `0`, `1`, and `2`.

The square room has walls of length `p` and a laser ray from the southwest corner first meets the east wall at a distance `q` from the `0th` receptor.

Given the two integers `p` and `q`, return _the number of the receptor that the ray meets first_.

The test cases are guaranteed so that the ray will meet a receptor eventually.

**Example 1:**

![](https://assets.glich.co/dsa/mirror-reflection/image0.png) 

**Input:** p = 2, q = 1
**Output:** 2
**Explanation:** The ray meets receptor 2 the first time it gets reflected back to the left wall.

**Example 2:**

**Input:** p = 3, q = 1
**Output:** 1

**Constraints:**

* `1 <= q <= p <= 1000`

# Approaches
## Simulation of Ray Path
This approach directly simulates the path of the laser ray. We can simplify the physics by tracking how many times the ray crosses the room horizontally (`extensions`) and what its total vertical displacement is. The ray starts at `(0,0)` and first hits the east wall at `(p,q)`. Each time it travels horizontally by `p`, it travels vertically by `q`. We can loop, incrementing the horizontal traversals and accumulating the vertical distance, until the ray's height is a multiple of `p`, which signifies it has landed on a corner.
**Time:** O(p) - In the worst-case scenario (when `p` and `q` are coprime), the loop will run `p` times before finding a solution. The number of iterations is `p / gcd(p, q)`. · **Space:** O(1) - We only use a few integer variables to store the state.
**Pros:** The logic is intuitive as it follows the physical path of the ray.; It avoids floating-point arithmetic, preventing precision issues.
**Cons:** The number of iterations depends on the input values `p` and `q`, and can be large. The time complexity is linear with respect to `p` in the worst case.; It is significantly less efficient than mathematical approaches for larger inputs.
### Explanation
We can model the ray's journey without using floating-point coordinates. Let's track the number of times the ray crosses the room from one vertical wall to the other, which we'll call `extensions`. We also track the total vertical distance traveled, `y`. 

Initially, `extensions = 0` and `y = 0`. In a loop, we simulate one horizontal traversal at a time. We increment `extensions` and add `q` to `y`. We then check if the ray has landed on a corner. A corner is located at height 0 or `p`. This occurs when the total vertical distance `y` is a multiple of `p`. 

When `y % p == 0`, we've found a corner. We then need to identify which one. 
- The number of horizontal traversals, `extensions`, tells us which vertical wall we're on. If `extensions` is odd, we're on the right wall (x=p). If `extensions` is even, we're on the left wall (x=0).
- The number of vertical traversals, `y / p`, tells us which horizontal wall we're on. If `y / p` is odd, we're on the top wall (y=p). If `y / p` is even, we're on the bottom wall (y=0).

By combining these two pieces of information, we can pinpoint the exact receptor and return its number.

```java
class Solution {
    public int mirrorReflection(int p, int q) {
        int extensions = 0;
        int y = 0;

        while (true) {
            extensions++;
            y += q;
            if (y % p == 0) {
                int reflections = y / p;
                if (extensions % 2 == 1) { // Right wall
                    if (reflections % 2 == 1) {
                        return 1; // Receptor 1 (p, p)
                    } else {
                        return 0; // Receptor 0 (p, 0)
                    }
                } else { // Left wall
                    // reflections must be odd to hit a receptor on the left wall
                    return 2; // Receptor 2 (0, p)
                }
            }
        }
    }
}
```
### Algorithm
1. Initialize state variables: `extensions = 0` to count horizontal room traversals and `y = 0` for the total vertical distance traveled.
2. Enter an infinite loop, as the problem guarantees a solution.
3. In each iteration, increment `extensions` by 1, representing the ray crossing the room horizontally one more time.
4. Add `q` to the total vertical distance `y`.
5. Check if the ray has hit a corner. A corner is hit when the total vertical distance `y` is a multiple of the room height `p`. This is checked with `y % p == 0`.
6. If a corner is hit:
    a. Calculate the number of vertical room traversals (or reflections off the top/bottom walls), `reflections = y / p`.
    b. Check the parity of `reflections` to determine if the ray hit the top wall (`reflections` is odd) or the bottom wall (`reflections` is even).
    c. Check the parity of `extensions` to determine if the ray hit the right wall (`extensions` is odd) or the left wall (`extensions` is even).
    d. Based on the combination of wall hits, determine the receptor and return its number:
        - Right wall, Top wall: Receptor 1.
        - Left wall, Top wall: Receptor 2.
        - Right wall, Bottom wall: Receptor 0.
        - Left wall, Bottom wall: This is the starting point, so the loop would have continued. This logic ensures we find the first receptor hit.

## Geometric Unfolding with GCD
A highly efficient way to solve this problem is to change the frame of reference. Instead of reflecting the laser ray, we can 'unfold' or 'unroll' the room. Imagine the plane is tiled with copies of the square room. The path of the laser, with all its reflections, becomes a single straight line in this tiled plane. The problem is then reduced to finding the first corner of any tiled room that this straight line passes through.
**Time:** O(log(min(p, q))) - The time complexity is dominated by the Euclidean algorithm for finding the GCD. · **Space:** O(1) - The iterative GCD algorithm uses constant extra space. A recursive implementation would use O(log(min(p,q))) stack space.
**Pros:** Extremely fast, with logarithmic time complexity.; Provides a direct, deterministic solution without any loops.; Mathematically elegant and robust.
**Cons:** Requires a conceptual leap to transform the reflection problem into a geometry problem on a grid.; Involves implementing or using a GCD function.
### Explanation
The laser starts at `(0,0)` and its path has a slope of `q/p`. The equation of this path in the unfolded grid is `Y = (q/p) * X`. We are looking for the first point `(X, Y)` on this line where `X` is a multiple of `p` and `Y` is also a multiple of `p`. Let this point be `(m*p, n*p)`. 

Plugging this into the line equation gives `n*p = (q/p) * (m*p)`, which simplifies to `n*p = m*q`. We are looking for the smallest positive integers `m` and `n` that satisfy this. This is equivalent to finding the least common multiple of `p` and `q`. We can find `m` and `n` by dividing the equation by `gcd(p, q)`:
`m * (q/gcd(p,q)) = n * (p/gcd(p,q))`
Since `p/gcd(p,q)` and `q/gcd(p,q)` are coprime, the smallest integer solution is:
`m = p / gcd(p, q)`
`n = q / gcd(p, q)`

Now, `m` represents the number of horizontal room traversals and `n` represents the vertical ones. The parity of `m` and `n` tells us the final corner:
- `m` odd, `n` odd -> `(p, p)` -> Receptor 1
- `m` even, `n` odd -> `(0, p)` -> Receptor 2
- `m` odd, `n` even -> `(p, 0)` -> Receptor 0
(Note: `m` and `n` cannot both be even, because `p/gcd` and `q/gcd` are coprime).

```java
class Solution {
    public int mirrorReflection(int p, int q) {
        int g = gcd(p, q);
        int m = p / g;
        int n = q / g;

        if (m % 2 == 0) { // m is even, n must be odd
            return 2;
        } else { // m is odd
            if (n % 2 == 1) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    // Euclidean algorithm to find GCD
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
1. Understand that reflecting a ray inside a room is equivalent to tiling the plane with copies of the room and letting the ray travel in a straight line.
2. The ray's path is a line from `(0,0)` with slope `q/p`, so its equation is `Y = (q/p) * X`.
3. The ray hits a corner of a tiled room when its coordinates `(X, Y)` are `(m*p, n*p)` for some integers `m` and `n`.
4. Substitute these coordinates into the line equation: `n*p = (q/p) * (m*p)`, which simplifies to `m*q = n*p`.
5. We need the smallest positive integers `m` and `n` that satisfy this equation. This is a classic Least Common Multiple (LCM) problem. The solution is `m = p / gcd(p, q)` and `n = q / gcd(p, q)`.
6. Determine the receptor based on the parity of `m` (number of horizontal room extensions) and `n` (number of vertical room extensions):
    - `m` is odd, `n` is odd: The ray hits the right wall (`x=p`) and the top wall (`y=p`). This is Receptor 1.
    - `m` is even, `n` is odd: The ray hits the left wall (`x=0`) and the top wall (`y=p`). This is Receptor 2.
    - `m` is odd, `n` is even: The ray hits the right wall (`x=p`) and the bottom wall (`y=0`). This is Receptor 0.
7. Implement a function to calculate the Greatest Common Divisor (GCD), for example, using the Euclidean algorithm.

## Optimized Mathematical Approach using Parity
This approach is a further optimization of the geometric method. It recognizes that the core of the problem lies in the parity of the room extension counts (`m` and `n`). Instead of computing the full Greatest Common Divisor (GCD), we can simplify `p` and `q` by repeatedly dividing out their common factors of 2. This is sufficient to determine the parities needed to identify the final receptor, leading to a very simple and fast algorithm.
**Time:** O(log(min(p, q))) - The number of divisions by 2 is limited by the number of bits in the smaller of `p` or `q`. · **Space:** O(1) - Only a few variables are used, requiring constant space.
**Pros:** The most efficient approach in terms of raw performance, as it uses simpler arithmetic operations (division by 2 and parity checks) than a full GCD.; The code is extremely concise and clean.
**Cons:** The reasoning behind why this simplification works is subtle and relies on number theory properties.
### Explanation
Building on the geometric approach, we know the result depends on the parity of `m = p/gcd(p,q)` and `n = q/gcd(p,q)`. Let's analyze the effect of factors of 2. 

Any common factor of 2 between `p` and `q` will be part of their GCD. We can simplify the fraction `p/q` by dividing both `p` and `q` by 2 until at least one of them becomes odd. This process is equivalent to dividing `p` and `q` by `2^k`, where `2^k` is the highest power of 2 that divides `gcd(p,q)`. 

After this simplification, let the new values be `p'` and `q'`. The remaining `gcd(p', q')` will be an odd number. When we compute `m = p'/gcd(p',q')`, dividing by an odd number does not change the parity. Thus, `parity(m) == parity(p')`. The same logic applies to `n`, so `parity(n) == parity(q')`. 

This means we can find the result by this simple procedure:
1. Remove all common factors of 2 from `p` and `q`.
2. Check the parity of the resulting `p` and `q` to find the answer.

This avoids the more complex multiplications and divisions of a full GCD algorithm, replacing them with simple bit shifts or divisions by 2.

```java
class Solution {
    public int mirrorReflection(int p, int q) {
        while (p % 2 == 0 && q % 2 == 0) {
            p /= 2;
            q /= 2;
        }

        // At this point, at least one of p or q is odd.

        if (p % 2 == 0) {
            // p is even, q must be odd.
            // m = p/g is even, n = q/g is odd.
            return 2;
        } else { // p is odd
            if (q % 2 == 1) {
                // p is odd, q is odd.
                // m = p/g is odd, n = q/g is odd.
                return 1;
            } else {
                // p is odd, q is even.
                // m = p/g is odd, n = q/g is even.
                return 0;
            }
        }
    }
}
```
### Algorithm
1. Observe that the final receptor depends only on the parity of `m = p/gcd(p,q)` and `n = q/gcd(p,q)`.
2. The key insight is that we can determine these parities without computing the full GCD. Any common factor of 2 in `p` and `q` will also be in `gcd(p,q)`. We can remove these common factors first.
3. Use a `while` loop to repeatedly divide both `p` and `q` by 2 as long as they are both even. This effectively removes the power-of-2 component from the GCD.
4. After the loop, the new `p` and `q` are not both even. Let's call them `p'` and `q'`. The remaining `gcd(p', q')` must be an odd number.
5. Since `m = p'/gcd(p',q')` and `gcd(p',q')` is odd, the parity of `m` is the same as the parity of `p'`. Similarly, the parity of `n` is the same as the parity of `q'`.
6. Therefore, we can simply check the parities of the simplified `p` and `q`:
    - If `p` is even (and `q` must be odd): This corresponds to `m` being even and `n` being odd. Return 2.
    - If `p` is odd and `q` is odd: This corresponds to `m` and `n` both being odd. Return 1.
    - If `p` is odd and `q` is even: This corresponds to `m` being odd and `n` being even. Return 0.

# Solutions
### Java

```java
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); }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
class Solution:
    def mirrorReflection(self, p: int, q: int) -> int: g = gcd(p, q) p = (p // g) % 2 q = (q // g) % 2 if p == 1 and q == 1: return 1 return 0 if p == 1 else 2

```