Problem Description

You are given a square room with mirrored walls of length p. There is a laser beam that starts at the southwest corner of the room (coordinate (0, 0)) and travels at a 45-degree angle towards the opposite wall. The room has three receptors located at the following corners:

• Receptor 0 at (p, 0)
• Receptor 1 at (p, p)
• Receptor 2 at (0, p)

The laser continues to bounce off the walls until it meets one of the receptors. You are also given an integer q, the vertical distance from the 0th receptor to where the laser first meets the east wall.

Your task is to return the number of the receptor that the laser beam will meet first.

Constraints:

• 1 <= p, q <= 1000

Thought Process

At first glance, the problem seems to require simulating the path of the laser as it bounces around the room. One could imagine tracing the path step by step, keeping track of the current position and direction after each bounce. However, this brute-force approach could be inefficient, especially as p and q grow larger.

To optimize, we need to recognize a pattern in the laser's movement. Instead of following each bounce, we can "unfold" the room: imagine extending the room by reflecting it repeatedly, so that the laser travels in a straight line through these virtual rooms. The problem then becomes finding when the laser's straight path will land on one of the receptors.

The key insight is to find the least common multiple (LCM) of p and q, since the laser will hit a receptor when it has traveled a vertical distance that is a multiple of p and a horizontal distance that is a multiple of q.

Solution Approach

Let's break down the algorithm step by step:

1. Find the LCM of p and q:
   • The laser will reach a corner when it has traveled a horizontal distance that is a multiple of p and a vertical distance that is a multiple of q.
   • The first such time is their LCM.
2. Count the number of room extensions:
   • Let m = LCM / p (number of room extensions horizontally).
   • Let n = LCM / q (number of room extensions vertically).
3. Determine which receptor is hit:
   • If m is even, the laser ends on the west wall (so receptor 2 is hit).
   • If n is even, the laser ends on the south wall (so receptor 0 is hit).
   • If both m and n are odd, the laser ends on the northeast corner (so receptor 1 is hit).
4. Return the receptor number based on the above logic.

This approach is efficient and avoids unnecessary simulation.

Example Walkthrough

Let's walk through an example with p = 3 and q = 1:

• LCM of 3 and 1 is 3.
• m = 3 / 3 = 1 (odd)
• n = 3 / 1 = 3 (odd)
• Both m and n are odd, so the laser hits receptor 1.

Step-by-step:

1. Laser starts at (0, 0) and moves at a 45-degree angle.
2. After 1 "room extension" horizontally (3 units), and 3 vertically (3 units), it reaches (3, 3), which is the northeast corner (receptor 1).

Time and Space Complexity

Brute-force Approach:

• Simulating each bounce would take up to O(p * q) steps in the worst case, which is inefficient for large values.
• Space complexity would be O(1), as we only need to keep track of the current position and direction.

• Finding the LCM and performing arithmetic calculations can be done in O(log(max(p, q))) time using the Euclidean algorithm for GCD.
• Space complexity is O(1), as we only use a few variables.

Summary

By recognizing that the laser's path forms a repeating pattern, we can avoid brute-force simulation and instead use mathematical reasoning to find the point of intersection. Calculating the LCM of p and q tells us when the laser will hit a corner, and simple parity checks determine which receptor is hit. This approach is both elegant and efficient, making the solution robust even for large inputs.

Code Implementation

def mirrorReflection(p: int, q: int) -> int:
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    
    lcm = p * q // gcd(p, q)
    m = lcm // p
    n = lcm // q
    if m % 2 == 0 and n % 2 == 1:
        return 2
    if m % 2 == 1 and n % 2 == 0:
        return 0
    if m % 2 == 1 and n % 2 == 1:
        return 1

class Solution {
public:
    int mirrorReflection(int p, int q) {
        int gcd = std::__gcd(p, q);
        int lcm = p * q / gcd;
        int m = lcm / p;
        int n = lcm / q;
        if (m % 2 == 0 && n % 2 == 1) return 2;
        if (m % 2 == 1 && n % 2 == 0) return 0;
        if (m % 2 == 1 && n % 2 == 1) return 1;
        return -1; // Should not reach here
    }
};

class Solution {
    public int mirrorReflection(int p, int q) {
        int gcd = gcd(p, q);
        int lcm = p * q / gcd;
        int m = lcm / p;
        int n = lcm / q;
        if (m % 2 == 0 && n % 2 == 1) return 2;
        if (m % 2 == 1 && n % 2 == 0) return 0;
        if (m % 2 == 1 && n % 2 == 1) return 1;
        return -1;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

var mirrorReflection = function(p, q) {
    function gcd(a, b) {
        while (b !== 0) {
            let t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
    let lcm = p * q / gcd(p, q);
    let m = lcm / p;
    let n = lcm / q;
    if (m % 2 === 0 && n % 2 === 1) return 2;
    if (m % 2 === 1 && n % 2 === 0) return 0;
    if (m % 2 === 1 && n % 2 === 1) return 1;
    return -1;
};