algoadvance

Leetcode 858. Mirror Reflection

Problem Statement

858. Mirror Reflection

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. The laser ray continues to bounce off the east and north walls until it eventually meets a receptor.

Return the number of the receptor that the laser ray will meet first.

Example 1:

Input: p = 2, q = 1
Output: 2
Explanation: The ray meets receptor 2 first after bouncing off the east wall and the north wall.

Example 2:

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

Note:

  1. 1 <= p <= 1000
  2. 0 <= q <= p

Clarifying Questions

  1. Understanding the Rebounding Path: The laser bounces between the east and north walls. Is it correct to assume the path reflects symmetrically?
  2. Receptors Location: The receptors are located at the northeast, southeast, and northwest corners labeled as 0, 1, and 2 respectively. Is this correct?

Code

public class Solution {
    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 != 0) {
            return 0;  // hitting receptor 0
        }
        if (m % 2 != 0 && n % 2 != 0) {
            return 1;  // hitting receptor 1
        }
        if (m % 2 != 0 && n % 2 == 0) {
            return 2;  // hitting receptor 2
        }
        
        return -1;  // this line theoretically should not be reached
    }
}

Strategy

  1. Symmetry and Reflection:
    • Consider the room and the path of the laser as an infinite grid with cells size p x p.
    • The laser ray reflects symmetrically, and we need to find the least common multiple (LCM) or the multiples where either m*p or n*q aligns perfectly with the cells.
  2. Determine First Receptor Hit:
    • The problem can be reduced to finding values m and n such that m*q = n*p.
    • This leads to finding the least common multiple of p and q via the Euclidean algorithm (GCD).
  3. Deducing Result:
    • Simplify the ratio m/n and check the parity (even or odd) values:
      • If n is odd and m is even, the laser hits receptor 0.
      • If both m and n are odd, the laser hits receptor 1.
      • If n is even and m is odd, the laser hits receptor 2.

Time Complexity

The time complexity is primarily determined by the while loop which divides by 2 until one of the numbers is odd. This loop is logarithmic with respect to p and q, hence the complexity is O(log(min(p, q))).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI