Skip to main content

858. Mirror Reflection

medium

In a square mirrored room of side p with three receptors at corners 0, 1, 2, a laser fires from corner 0 at height q. Which receptor does it hit first? Unfold the reflections; the answer drops out of parity on p / gcd(p, q) and q / gcd(p, q).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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, labeled 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. Given the two integers p and q, return the number of the receptor that the ray meets first.

Constraints

  • 1 <= q <= p <= 1000

Examples

Example 1

Input
p = 2, q = 1
Output
2

Explanation: The ray meets receptor 2 the first time it gets reflected back to the left wall.

Example 2

Input
p = 3, q = 1
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Unfolding trick: instead of reflecting the ray, imagine stacking copies of the room. The ray travels in a straight line at slope q / p.

Hint 2

The ray hits a corner when its position is at an integer multiple of p both horizontally and vertically. Find the smallest m such that m*q is a multiple of p.

Hint 3

Let g = gcd(p, q). Then m = p / g (the smallest m with m*q being a multiple of p).

Hint 4

Receptor depends on the parities of m = p / g and n = q * m / p = q / g. (m, n) parities (even/odd) map to receptor 2/1/0.

Solution approach

Reveal approach

Unfold the reflections into a straight ray. The ray heads from (0, 0) toward (p, q) and continues until it lands on a corner. After m horizontal moves it has covered horizontal distance m*p and vertical distance m*q. We need m*q to be a multiple of p so the ray lands at a vertical multiple of p (a corner row). Smallest such m is m = p / gcd(p, q). Let n = m * q / p = q / gcd(p, q). Now (m parity, n parity) classifies which corner: (odd, odd) -> 1, (even, odd) -> 0, (odd, even) -> 2. Cases: if m % 2 == 0, receptor 0 (impossible per spec, but stated for completeness); if m % 2 == 1 and n % 2 == 0, receptor 2; if m % 2 == 1 and n % 2 == 1, receptor 1. O(log min(p, q)) time for gcd, O(1) space.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • math
  • geometry
  • number-theory

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Mirror Reflection and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →