By Long Luo

This article is the solution 3 Approaches: BFS(Dijkstra), Binary Search, Union Find of Problem 858. Mirror Reflection.

Intuition

What if we assume the Ray Not Reflected and Keeps Going?

Consider that there is a mirrored world behind the mirror, we can expand the room behind the mirror. The ray has not been reflected and keep going cross the room.

As the image below shows, we can easily know which receptor will the ray will meet first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int mirrorReflection(int p, int q) {
        if (p == q) {
            return 1;
        }

        if (q == 0) {
            return 0;
        }

        int lcm = p * q / gcd(p, q);
        int x = lcm / p;
        int y = lcm / q;

        if (x % 2 == 1 && y % 2 == 1) {
            return 1;
        } else if (x % 2 == 0 && y % 2 == 1) {
            return 0;
        } else {
            return 2;
        }
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Analysis

• Time Complexity: \(O(1)\)
• Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗