Mirror Reflection

Med

#0812Time: 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.

Patterns

Math Geometry Number Theory

Prompt

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 0^th 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:

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

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

Initialize state variables: extensions = 0 to count horizontal room traversals and y = 0 for the total vertical distance traveled.
Enter an infinite loop, as the problem guarantees a solution.
In each iteration, increment extensions by 1, representing the ray crossing the room horizontally one more time.
Add q to the total vertical distance y.
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.
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.

Walkthrough

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.

1class Solution {2    public int mirrorReflection(int p, int q) {3        int extensions = 0;4        int y = 0;5 6        while (true) {7            extensions++;8            y += q;9            if (y % p == 0) {10                int reflections = y / p;11                if (extensions % 2 == 1) { // Right wall12                    if (reflections % 2 == 1) {13                        return 1; // Receptor 1 (p, p)14                    } else {15                        return 0; // Receptor 0 (p, 0)16                    }17                } else { // Left wall18                    // reflections must be odd to hit a receptor on the left wall19                    return 2; // Receptor 2 (0, p)20                }21            }22        }23    }24}

Complexity

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.

Trade-offs

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.

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.

Algorithm

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.
The ray's path is a line from (0,0) with slope q/p, so its equation is Y = (q/p) * X.
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.
Substitute these coordinates into the line equation: n*p = (q/p) * (m*p), which simplifies to m*q = n*p.
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).
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.
Implement a function to calculate the Greatest Common Divisor (GCD), for example, using the Euclidean algorithm.

Walkthrough

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).

1class Solution {2    public int mirrorReflection(int p, int q) {3        int g = gcd(p, q);4        int m = p / g;5        int n = q / g;6 7        if (m % 2 == 0) { // m is even, n must be odd8            return 2;9        } else { // m is odd10            if (n % 2 == 1) {11                return 1;12            } else {13                return 0;14            }15        }16    }17 18    // Euclidean algorithm to find GCD19    private int gcd(int a, int b) {20        while (b != 0) {21            int temp = b;22            b = a % b;23            a = temp;24        }25        return a;26    }27}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Observe that the final receptor depends only on the parity of m = p/gcd(p,q) and n = q/gcd(p,q).
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.
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.
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.
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'.
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.

Walkthrough

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:

Remove all common factors of 2 from p and q.
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.

1class Solution {2    public int mirrorReflection(int p, int q) {3        while (p % 2 == 0 && q % 2 == 0) {4            p /= 2;5            q /= 2;6        }7 8        // At this point, at least one of p or q is odd.9 10        if (p % 2 == 0) {11            // p is even, q must be odd.12            // m = p/g is even, n = q/g is odd.13            return 2;14        } else { // p is odd15            if (q % 2 == 1) {16                // p is odd, q is odd.17                // m = p/g is odd, n = q/g is odd.18                return 1;19            } else {20                // p is odd, q is even.21                // m = p/g is odd, n = q/g is even.22                return 0;23            }24        }25    }26}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int mirrorReflection(int p, int q) {4    int g = gcd(p, q);5    p = (p / g) % 2;6    q = (q / g) % 2;7    if (p == 1 && q == 1) {8      return 1;9    }10    return p == 1 ? 0 : 2;11  }12private13  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }14}

1class Solution {2public:3  int mirrorReflection(int p, int q) {4    int g = __gcd(p, q);5    p = (p / g) % 2;6    q = (q / g) % 2;7    if (p == 1 && q == 1) {8      return 1;9    }10    return p == 1 ? 0 : 2;11  }12};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int mirrorReflection(int p, int q) {4    int g = gcd(p, q);5    p = (p / g) % 2;6    q = (q / g) % 2;7    if (p == 1 && q == 1) {8      return 1;9    }10    return p == 1 ? 0 : 2;11  }12private13  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }14}

1class Solution {2public:3  int mirrorReflection(int p, int q) {4    int g = __gcd(p, q);5    p = (p / g) % 2;6    q = (q / g) % 2;7    if (p == 1 && q == 1) {8      return 1;9    }10    return p == 1 ? 0 : 2;11  }12};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.