Mirror Reflection Python Solution with Tests

Tested Python solution for LeetCode 858 with 21 pytest cases. Generate a practice environment with lcpy.

LeetCode 858, Medium. Topics: Math, Geometry, Number Theory. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 21 parametrized pytest cases, and a playground notebook:

lcpy gen -n 858   # by problem number
lcpy gen -s mirror_reflection   # by problem name

​

Problem

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.

​

Examples

Input: p = 2, q = 1
Output: 2
Explanation: The ray meets receptor 2 the first time it gets reflected back to the left wall.

Input: p = 3, q = 1
Output: 1

​

Constraints

• 1 <= q <= p <= 1000

Follow up: Could you solve it without simulating the reflections?

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from math import gcd


class Solution:
    # Time: O(log(min(p, q)))
    # Space: O(1)
    def mirror_reflection(self, p: int, q: int) -> int:
        g = gcd(p, q)
        heights, crossings = q // g, p // g
        if heights % 2 == 0:
            return 0
        return 2 if crossings % 2 == 0 else 1

​

Complexity

Time	Space
O(log(min(p, q)))	O(1)

​

Tags