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 0th receptor.

Return the number of the receptor that the ray meets first. (It is guaranteed that the ray will meet a receptor eventually.)

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

- 1 <= p <= 1000
- 0 <= q <= p

Solution:

The idea comes from this post: https://leetcode.com/problems/mirror-reflection/discuss/141773, and here I add some explanation.

public int mirrorReflection(int p, int q) { int m = 1, n = 1; while(m * p != n * q){ n++; m = n * q / p; } if (m % 2 == 0 && n % 2 == 1) return 0; if (m % 2 == 1 && n % 2 == 1) return 1; if (m % 2 == 1 && n % 2 == 0) return 2; return -1; }

First, think about the case p = 3 & q = 2.

So, this problem can be transformed into finding m * p = n * q, where

m = the number of room extension + 1.

n = the number of light reflection + 1.

So, this problem can be transformed into finding m * p = n * q, where

m = the number of room extension + 1.

n = the number of light reflection + 1.

- If the number of light reflection is odd (which means n is even), it means the corner is on the left-hand side. The possible corner is 2.

Otherwise, the corner is on the right-hand side. The possible corners are 0 and 1. - Given the corner is on the right-hand side.

If the number of room extension is even (which means m is odd), it means the corner is 1. Otherwise, the corner is 0.

So, we can conclude:

m is even & n is odd => return 0. m is odd & n is odd => return 1. m is odd & n is even => return 2.

Note: The case m is even & n is even is impossible. Because in the equation m * q = n * p, if m and n are even, we can divide both m and n by 2. Then, m or n must be odd.

--

Because we want to find m * p = n * q, where either m or n is odd, we can do it this way.

Because we want to find m * p = n * q, where either m or n is odd, we can do it this way.

public int mirrorReflection(int p, int q) { int m = q, n = p; while(m % 2 == 0 && n % 2 == 0){ m /= 2; n /= 2; } if (m % 2 == 0 && n % 2 == 1) return 0; if (m % 2 == 1 && n % 2 == 1) return 1; if (m % 2 == 1 && n % 2 == 0) return 2; return -1; }