algoadvance

Leetcode 858. Mirror Reflection

Problem Statement

You are given a two-dimensional square room of size p x p and a laser ray that starts from the corner (0, 0) and runs diagonally in the direction of (p, p). There are mirrors on the walls of the room. The laser ray reflects off the mirrors until it finally hits a receptor at one of the corners of the room.

There are three receptors in the room as follows:

Your task is to determine which receptor the laser ray will meet first. The square room has a symmetric property where the laser can reflect in different patterns. Given the side length p of the square and the distance q the laser first travels vertically to the opposite wall, return the number 0, 1, or 2 corresponding to which receptor the laser will meet first.

Clarifying Questions

  1. Is p always a positive integer?
  2. Is q always a positive integer and less than or equal to p?
  3. Do the laser reflections continue indefinitely until they meet a receptor?

(Assuming yes to all questions as they are typical constraints for such problems.)

Strategy

  1. The room’s reflections can be understood by extending the room in an infinite grid of p x p squares. The point (m*p, n*p) where the laser ray lands after reflections can be determined by tracking multiples of p.
  2. The endpoints landing condition depends on the relative proportion of travels in horizontal and vertical distances.
  3. You need to find the least common multiple (LCM) of p and q to determine when the ray hits the edge.

Steps:

  1. Compute m and n such that mp and nq` are the first common points.
  2. Check if m and n are even or odd:
    • (even, odd) -> Receptor 0
    • (odd, odd) -> Receptor 1
    • (odd, even) -> Receptor 2

Equation:

Code

#include <iostream>
#include <algorithm> // for std::gcd

class Solution {
public:
    int mirrorReflection(int p, int q) {
        int gcd_pq = std::gcd(p, q);
        int lcm_pq = (p * q) / gcd_pq;
        int m = lcm_pq / p;
        int n = lcm_pq / q;
        
        if (m % 2 == 0 && n % 2 == 1) {
            return 0;
        } else if (m % 2 == 1 && n % 2 == 1) {
            return 1;
        } else if (m % 2 == 1 && n % 2 == 0) {
            return 2;
        }
        return -1; // Just a safe return; the problem's nature should never hit this case.
    }
};

int main() {
    Solution solution;
    std::cout << solution.mirrorReflection(2, 1) << std::endl; // Output: 2
    std::cout << solution.mirrorReflection(3, 1) << std::endl; // Output: 1
    return 0;
}

Time Complexity

Thus, the overall time complexity is O(log(min(p, q))) due to the GCD calculation.

This code computes which receptor will be the first one the ray meets by considering the laser reflections’ properties and geometry within a room.

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