Problem Description

You have a square room with mirrors on all four walls. The room has side length p. There are receptors at three corners of the room:

• Receptor 0: at the southeast corner (bottom-right)
• Receptor 1: at the northeast corner (top-right)
• Receptor 2: at the northwest corner (top-left)
• The southwest corner (bottom-left) has no receptor

A laser ray starts from the southwest corner and travels at an angle. The ray first hits the east wall at a distance q from the bottom (where receptor 0 is located).

When the laser hits a wall, it reflects off the mirror and continues traveling. The ray will bounce around the room until it eventually hits one of the three receptors.

Given integers p (the side length of the square room) and q (the height at which the ray first hits the east wall), determine which receptor (0, 1, or 2) the laser ray will hit first.

The problem guarantees that the ray will eventually hit a receptor.

Example visualization:

• If p = 2 and q = 1, the ray starts from the southwest corner, hits the east wall at height 1 (halfway up), reflects, and continues bouncing until it reaches one of the receptors.

The solution uses the greatest common divisor (GCD) of p and q to reduce the problem. After dividing both values by their GCD, it checks the parity (odd/even nature) of the reduced values to determine which receptor is hit:

• If both reduced p and q are odd, the ray hits receptor 1
• If reduced p is odd and q is even, the ray hits receptor 0
• If reduced p is even, the ray hits receptor 2

Intuition

To understand how the laser ray behaves, imagine "unfolding" the room's reflections. Instead of the ray bouncing off mirrors, we can visualize it as traveling in a straight line through multiple copies of the room arranged in a grid pattern.

When we unfold the reflections:

• Each reflection off a vertical wall is like moving to the next room horizontally
• Each reflection off a horizontal wall is like moving to the next room vertically
• The rooms alternate in a checkerboard pattern with receptors at different corners

The ray travels from the origin (0, 0) in a straight line with slope q/p. It will hit a receptor when it reaches a point where both coordinates are multiples of p (at a corner of some unfolded room).

The first such point occurs at coordinates that are the least common multiple (LCM) of p and q. We can express this as:

• x-coordinate: LCM(p, q) * (p / q) = LCM(p, q) / q * p
• y-coordinate: LCM(p, q)

Since LCM(p, q) = p * q / GCD(p, q), we can simplify by dividing both p and q by their GCD. This gives us the minimal number of "room crossings" needed.

After reduction by GCD:

• If we cross an odd number of rooms horizontally (p/GCD is odd) and an odd number vertically (q/GCD is odd), we end up at the top-right → receptor 1
• If we cross an odd number horizontally but even number vertically, we stay at the bottom-right → receptor 0
• If we cross an even number horizontally, we end up on the left side (top-left) → receptor 2

The parity (odd/even nature) of these reduced values directly tells us which receptor the ray hits, leading to the elegant solution using modulo 2 operations.

Learn more about Math patterns.

Solution Approach

The implementation follows directly from our intuition about unfolding the reflections and checking parities:

1. Calculate the GCD: First, we find the greatest common divisor of p and q using the built-in gcd function. This helps us reduce the problem to its simplest form.

2. Reduce to parity check: We divide both p and q by their GCD and then take modulo 2 to get their parities (0 for even, 1 for odd):

   p = (p // g) % 2
   q = (q // g) % 2

   This tells us whether we cross an odd or even number of rooms in each direction.

3. Determine the receptor based on parities:

   • If both p and q are 1 (both odd): The ray crosses an odd number of rooms both horizontally and vertically, landing at the northeast corner → return receptor 1

   • If p is 1 and q is 0 (horizontal odd, vertical even): The ray crosses an odd number of rooms horizontally but even vertically, staying on the right side at the bottom → return receptor 0

   • If p is 0 (horizontal even): The ray crosses an even number of rooms horizontally, ending up on the left side at the top → return receptor 2

The solution elegantly condenses this logic into just a few lines:

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

This approach has O(log(min(p, q))) time complexity for the GCD calculation and O(1) space complexity, making it highly efficient.

Example Walkthrough

Let's trace through an example with p = 6 and q = 4.

Step 1: Calculate GCD

• GCD(6, 4) = 2

Step 2: Reduce by GCD and find parities

• p_reduced = 6 / 2 = 3
• q_reduced = 4 / 2 = 2
• p_parity = 3 % 2 = 1 (odd)
• q_parity = 2 % 2 = 0 (even)

Step 3: Determine receptor based on parities

• Since p_parity = 1 (odd) and q_parity = 0 (even), we have the case where we cross an odd number of rooms horizontally and an even number vertically.
• This means the laser stays on the right side but at the bottom.
• Therefore, the laser hits receptor 0.

Visualization of the unfolding: If we unfold the reflections, the laser travels in a straight line from (0,0) with slope 4/6 = 2/3. After reduction by GCD, we need to cross 3 rooms horizontally and 2 rooms vertically to reach a corner. Since 3 is odd and 2 is even, we end up at the bottom-right corner where receptor 0 is located.

Another example with p = 3 and q = 3:

Step 1: Calculate GCD

• GCD(3, 3) = 3

Step 2: Reduce by GCD and find parities

• p_reduced = 3 / 3 = 1
• q_reduced = 3 / 3 = 1
• p_parity = 1 % 2 = 1 (odd)
• q_parity = 1 % 2 = 1 (odd)

Step 3: Determine receptor based on parities

• Since both p_parity = 1 and q_parity = 1 (both odd), we cross an odd number of rooms in both directions.
• This places us at the top-right corner.
• Therefore, the laser hits receptor 1.

In this case, the laser travels at a 45-degree angle (slope = 1) and after reduction, needs just 1 room crossing in each direction to hit the northeast corner.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log(min(p, q)))

The time complexity is dominated by the gcd(p, q) operation, which uses the Euclidean algorithm. The Euclidean algorithm has a time complexity of O(log(min(p, q))). The remaining operations after computing the GCD are constant time operations:

• Integer division p // g and q // g: O(1)
• Modulo operations % 2: O(1)
• Conditional checks and return statements: O(1)

Therefore, the overall time complexity is O(log(min(p, q))).

Space Complexity: O(1)

The space complexity is constant as the algorithm only uses a fixed amount of extra space:

• Variable g to store the GCD result: O(1)
• Variables p and q are reused (modified in place): O(1)
• No recursive calls in the main function (though gcd might use recursion internally, modern Python implementations use iteration): O(1)

The algorithm doesn't create any data structures that grow with the input size, so the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Import GCD Function

One of the most common mistakes is forgetting to import the gcd function, leading to a NameError at runtime.

Incorrect:

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        g = gcd(p, q)  # NameError: name 'gcd' is not defined
        # rest of the code...

Correct:

from math import gcd  # Don't forget this import!

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        g = gcd(p, q)
        # rest of the code...

2. Confusing Variable Names After Reduction

A frequent pitfall is reusing the same variable names p and q after reduction, which can lead to confusion about whether you're working with the original values or the parities.

Potentially Confusing:

g = gcd(p, q)
p = (p // g) % 2  # p now represents parity, not the original value
q = (q // g) % 2  # q now represents parity, not the original value

Clearer Alternative:

g = gcd(p, q)
p_parity = (p // g) % 2  # Clear that this is the parity
q_parity = (q // g) % 2  # Clear that this is the parity

if p_parity == 1 and q_parity == 1:
    return 1
return 0 if p_parity == 1 else 2

3. Incorrect Parity Logic

Some might mistakenly think they need to check if the reduced values themselves are odd/even before taking modulo 2, leading to redundant or incorrect code.

Incorrect Understanding:

g = gcd(p, q)
reduced_p = p // g
reduced_q = q // g

# Wrong: checking oddness before taking modulo
if reduced_p % 2 == 1 and reduced_q % 2 == 1:
    return 1
# This works but is redundant

Correct and Concise:

g = gcd(p, q)
p = (p // g) % 2  # Directly get parity
q = (q // g) % 2
# Continue with logic...

4. Edge Case Handling Assumptions

While the problem guarantees the ray will hit a receptor, some might try to add unnecessary edge case handling for when GCD equals 0 or when p and q are equal, complicating the solution unnecessarily.

Overcomplicated:

if p == 0 or q == 0:  # Unnecessary - problem guarantees valid input
    return -1
if p == q:  # Unnecessary special case
    return 1
g = gcd(p, q)
# rest of the code...

Simple and Correct: Trust the problem constraints and keep the solution clean without unnecessary checks.