How does the Mirror Reflection problem involve math and geometry?

The problem combines principles of geometry and math, specifically reflection patterns and modular arithmetic, to find the receptor where the laser will hit first.

What is the best approach to solve the Mirror Reflection problem?

The most efficient solution involves using modular arithmetic to simulate the laser’s path and calculate the first receptor it hits, avoiding unnecessary simulations.

What are the common pitfalls when solving Mirror Reflection?

Candidates often struggle with inefficient brute-force solutions or fail to recognize the benefits of applying geometric and modular principles to the problem.

Can Mirror Reflection be solved using brute force?

While brute force is possible, it is inefficient, and solutions using geometry and modular arithmetic are much faster and scalable.

How can GhostInterview help with Mirror Reflection practice?

GhostInterview aids by walking through the core concepts of laser reflections, offering solutions that highlight optimization techniques like modular arithmetic.

#858

Medium

auto_awesome数学·结合·几何

LeetCode 题解工作台

镜面反射

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0 ， 1 ，以及 2 。正方形房间的墙壁长度为 p ，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。示例…

数学几何数论

题目描述

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。

正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。

返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。

示例 1：

输入：p = 2, q = 1
输出：2
解释：这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。

示例 2：

输入：p = 3, q = 1
输入：1

提示：

1 <= q <= p <= 1000

lightbulb

解题思路

方法一：数学

根据题意，光线在每次反射时，都会向上或向下移动 $q$ 的距离，向右移动 $p$ 的距离。而由于光线最后一定会遇到接收器，因此，我们需要找到一个最小的 $k$ ，使得 $k \times q$ 是 $p$ 的倍数。

同时，根据 $k$ 的奇偶性，我们可以确定光线最终到达了西侧还是东侧。如果 $k$ 是偶数，那么光线最终到达的是西侧，否则光线最终到达的是东侧。

另外，根据 $k \times q$ 除以 $p$ 的结果的奇偶性，我们可以确定光线最终到达的是北侧还是南侧。如果 $k \times q$ 是 $p$ 的偶数倍，那么光线最终到达的是南侧，否则光线最终到达的是北侧。

时间复杂度 $O(\log p)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of geometry and modular arithmetic.
question_mark
Check if the candidate approaches the problem by first simulating the reflections.
question_mark
Evaluate whether the candidate considers optimizing the solution using math-based reflection patterns.

warning

常见陷阱

外企场景

error
Forgetting that the laser will eventually meet a receptor after a certain number of reflections, leading to inefficient simulation approaches.
error
Not fully understanding the geometric pattern of laser reflections and attempting brute-force methods.
error
Ignoring modular arithmetic’s role in optimizing the solution, leading to unnecessary calculations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Different input values for p and q may lead to various patterns in laser reflections.
arrow_right_alt
The problem can be extended to more complex room shapes or other configurations of mirrors.
arrow_right_alt
You can explore performance optimizations by analyzing larger values for p and q.

help

常见问题

外企场景

继续练习

#866 回文质数 #836 矩形重叠 #883 三维形体投影面积