Solution


Approach 1: Simulation

Intuition

The initial ray can be described as going from an origin (x, y) = (0, 0) in the direction (rx, ry) = (p, q). From this, we can figure out which wall it will meet and where, and what the appropriate new ray will be (based on reflection.) We keep simulating the ray until it finds it's destination.

Algorithm

The parameterized position of the laser after time t will be (x + rx * t, y + ry * t). From there, we know when it will meet the east wall (if x + rx * t == p), and so on. For a positive (and nonnegligible) time t, it meets the next wall.

We can then calculate how the ray reflects. If it hits an east or west wall, then rx *= -1, else ry *= -1.

In Java, care must be taken with floating point operations.

Complexity Analysis

  • Time Complexity: . We can prove (using Approach #2) that the number of bounces is bounded by this.

  • Space Complexity: .


Approach 2: Mathematical

Intuition and Algorithm

Instead of modelling the ray as a bouncing line, model it as a straight line through reflections of the room.

For example, if p = 2, q = 1, then we can reflect the room horizontally, and draw a straight line from (0, 0) to (4, 2). The ray meets the receptor 2, which was reflected from (0, 2) to (4, 2).

In general, the ray goes to the first integer point (kp, kq) where k is an integer, and kp and kq are multiples of p. Thus, the goal is just to find the smallest k for which kq is a multiple of p.

The mathematical answer is k = p / gcd(p, q).

Complexity Analysis

  • Time Complexity: , the complexity of the gcd operation.

  • Space Complexity: .


Analysis written by: @awice.