Mirror Reflection

This problem can be approached by understanding how the ray moves in the room. We can extend the room virtually by mirroring it multiple times. This way, we can see that the ray moves in a straight line.

We need to determine when the ray reaches one of the receptors for the first time. This happens when the ray reaches a corner of the room.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        from math import gcd

        # Find the greatest common divisor of p and q
        g = gcd(p, q)
        p = p // g  # Dividing p and q by the greatest common divisor
        q = q // g

        # If p is odd and q is even, the ray meets receptor 0
        if p % 2 == 1 and q % 2 == 0:
            return 0

        # If p is odd and q is odd, the ray meets receptor 1
        if p % 2 == 1 and q % 2 == 1:
            return 1

        # If p is even and q is odd, the ray meets receptor 2
        if p % 2 == 0 and q % 2 == 1:
            return 2

The code first computes the greatest common divisor of p and q and divides both by that value. Then, depending on the parity of p and q, the function returns the receptor number that the ray meets first.

The time complexity is O(log min(p, q)) due to the gcd computation, and the space complexity is O(1), as only a constant amount of extra space is used.