{x}
blog image

Mirror Reflection

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:

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

Solution Explanation for Mirror Reflection

This problem involves understanding the reflection of a laser beam in a square room. The goal is to determine which receptor (0, 1, or 2) the beam first hits. The solution leverages the concept of the greatest common divisor (GCD) and modular arithmetic to efficiently determine the receptor.

Core Idea:

The key insight is that the path of the laser beam can be analyzed using the ratio of p (room size) and q (initial intersection point). The behavior repeats periodically. By finding the GCD of p and q, we effectively determine the fundamental repeating pattern. Then, looking at the remainders when p and q are divided by the GCD, modulo 2, simplifies the problem to a few cases.

Algorithm:

  1. Calculate GCD: Find the greatest common divisor (g) of p and q using Euclid's algorithm.

  2. Reduce and Modulo: Divide both p and q by g and then take the modulo 2 of the results. This step essentially normalizes the problem and reduces the possibilities to four cases based on the parity (even or odd) of the reduced p and q.

  3. Determine Receptor: Based on the remainders:

    • If both p % 2 and q % 2 are 1, the receptor is 1.
    • If p % 2 is 1 and q % 2 is 0, the receptor is 0.
    • If p % 2 is 0 and q % 2 is 1, the receptor is 2. (This case is implied by the code's structure)

Time and Space Complexity:

  • Time Complexity: O(log(min(p, q))). This is dominated by the GCD calculation, which uses Euclid's algorithm. The time complexity of Euclid's algorithm is logarithmic with respect to the smaller input.

  • Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store variables.

Code Explanation (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
 
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

The gcd function implements Euclid's algorithm for finding the greatest common divisor. The mirrorReflection function then performs the steps described above: calculating the GCD, reducing and taking the modulo, and finally determining the receptor number. The conditional logic efficiently handles the different cases based on the remainders.

The Java, C++, Go, and TypeScript code implementations follow the same algorithm and logic as the Python example; only the syntax differs slightly based on the specific language. They all achieve the same time and space complexity.