Leetcode 858. Mirror Reflection

Problem Explanation

In this problem, a square room with walls of length 'p' is given where a laser ray is shot from the southwest corner towards the east wall. The beam could hit anywhere along the east wall. After the initial hit, the beam will start reflecting off the walls. The task is to find the receptor (out of receptors numbered 0, 1, 2 placed at corners except the southwest corner) that the beam hits first.

If we visualize this, it could be seen that the beam will eventually hit one of the receptors after multiple reflections. So, we need to figure out the first receptor it touches.

The room's length is 'p', and the first time laser hits the east wall at distance q from the 0th receptor.

This problem requires using mathematical properties and observations rather than algorithms or data structures.

Walk Through an Example

Let's take an example with input p = 2, q = 1.

The beam direction initially is from southwest towards the east wall (picture it as if it's from bottom left corner towards right). It first hits the east wall 1 unit away from the 0th receptor (since q=1 and wall length is p=2). After reflecting from east wall, it heads towards the north wall, where it will hit exactly at the corner where receptor 2 is placed. This is the first receptor that the beam hit in its journey. Thus, the output will be 2.

Approach

The approach is to keep dividing both 'p' and 'q' by 2 until we are left with odd numbers (since reflections are symmetrical around the center). This is to simplify the paths and calculate the receptor the laser will hit.

By the end of this process, one can see the following patterns:

  • If 'p' is still even, it means there's a vertical symmetry and the beam does not touch the north wall. Hence, the first receptor it hits will be 2.
  • If 'q' is still even, the beam does not touch the east wall. Hence, the first receptor it hits will be 0.
  • Else, the first receptor it hits will be 1.

Python Solution

1
2python
3class Solution:
4    def mirrorReflection(self, p: int, q: int) -> int:
5        ## Divide p and q by 2 till any of them is odd
6        while (p % 2 == 0 and q % 2 == 0):
7            p //= 2
8            q //= 2
9        ## if p is even, return 2
10        if p % 2 == 0:
11            return 2
12        ## if q is even, return 0
13        elif q % 2 == 0:
14            return 0
15        ## else, return 1
16        else:
17            return 1

Java Solution

1
2java
3public class Solution {
4    public int mirrorReflection(int p, int q) {
5        while (p % 2 == 0 && q % 2 == 0) {
6            p /= 2;
7            q /= 2;
8        }
9        if (p % 2 == 0) {
10            return 2;
11        } else if (q % 2 == 0) {
12            return 0;
13        } else {
14            return 1;
15        }
16    }
17}

JavaScript Solution

1
2javascript
3var mirrorReflection = function(p, q) {
4    while (p % 2 === 0 && q % 2 === 0) {
5        p /= 2;
6        q /= 2;
7    }
8    if (p % 2 === 0) {
9        return 2;
10    } else if (q % 2 === 0) {
11        return 0;
12    } else {
13        return 1;
14    }
15};

CPP Solution

1
2cpp
3class Solution {
4public:
5    int mirrorReflection(int p, int q) {
6        while (p % 2 == 0 && q % 2 == 0) {
7            p /= 2;
8            q /= 2;
9        }
10        if (p % 2 == 0) {
11            return 2;
12        } else if (q % 2 == 0) {
13            return 0;
14        } else {
15            return 1;
16        }
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public int MirrorReflection(int p, int q) {
5        while (p % 2 == 0 && q % 2 == 0) {
6            p /= 2;
7            q /= 2;
8        }
9        if (p % 2 == 0) {
10            return 2;
11        } else if (q % 2 == 0) {
12            return 0;
13        } else {
14            return 1;
15        }
16    }
17}

Conclusion

This problem highlights the power of pattern recognition in problem-solving. It blends simple mathematics and looping control to devise a rules-based system for determining which receptor the laser will hit first. The problem is easy to understand but requires careful pondering to arrive at the appropriate pattern. This helps in improving both mathematical reasoning and coding skills.Such problems can seem intimidating due to the nature of their description, but once you start working towards the solution and unravel their patterns, you will find that they are solvable even with basic coding skills.

The solutions provided use Python, Java, JavaScript, C++ and C#, covering most of the widely-used coding languages. This will help the readers to interpret the solution in the programming language they are comfortable with.

The key to solving such problems is to first visualize the problem (creating a mental image or drawing it out), identify patterns and then start coding. Practicing such problems can significantly enhance your creativity, pattern recognition, and programming skills. As this example illustrates, programming is not just about knowing syntax and programming constructs but also about problem-solving and logical reasoning.

In the future, we will continue to discuss more of such problems involving mathematical properties, algorithms, algorithms or data structures, because they not only help you improve as a programmer but also enhance your analytical and logical skills, which are quintessential for being a good software developer and problem-solver.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫