Mirror Reflection - Practice Coding Problems

Mirror Reflection - 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, 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.

Given the two integers p and q, return the number of the receptor that the ray meets first.

The test cases are guaranteed so that the ray will meet a receptor eventually.

Input & Output

Example 1 — Basic Case

$ Input: p = 2, q = 1

› Output: 2

💡 Note: The ray starts at (0,0) and first hits the east wall at (2,1). After bouncing, it eventually reaches receptor 2 at the northwest corner (0,2).

Example 2 — Different Path

$ Input: p = 3, q = 1

› Output: 1

💡 Note: The ray bounces multiple times but eventually hits receptor 1 at the northeast corner (3,3).

Example 3 — Direct Hit

$ Input: p = 1, q = 1

› Output: 1

💡 Note: The ray travels diagonally and directly hits receptor 1 at (1,1) without any bounces.

Constraints

1 ≤ p ≤ 1000
0 < q < p

Visualization

Tap to expand

Understanding the Visualization

Square Room Setup

Room with mirrors and 3 receptors at corners

Laser Path

Ray bounces off mirrors following reflection laws

Hit Receptor

Determine which receptor (0, 1, or 2) is hit first

Key Takeaway

🎯 Key Insight: Use GCD to reduce the problem and parity rules to find the receptor directly

Asked in

G Google 15 f Facebook 8

The key insight is that instead of simulating the laser bounces, we can use mathematical properties. After reducing p and q by their GCD, the parity (even/odd) of the reduced values determines which receptor is hit. Best approach uses GCD calculation. Time: O(log(min(p,q))), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(p+q)	O(1)	Simulate the laser ray bouncing off walls until it hits a receptor
Mathematical GCD Approach	O(log(min(p,q)))	O(1)	Use mathematical properties and GCD to determine which receptor is hit

Simulation Approach — Algorithm Steps

Start at southwest corner (0,0) with direction (q,p)
Simulate bouncing off walls by flipping direction
Continue until hitting a corner with receptor

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Laser starts at southwest corner (0,0)

Bounce Simulation

Calculate reflections off each wall

Find Receptor

Stop when hitting a corner with receptor

Code -

solution.c — C

#include <stdio.h>
#include <math.h>

int solution(int p, int q) {
    double x = 0, y = 0;
    double dx = q, dy = p;
    
    while (1) {
        double t_x = dx > 0 ? (p - x) / dx : -x / dx;
        double t_y = dy > 0 ? (p - y) / dy : -y / dy;
        
        double t = fmin(t_x, t_y);
        
        x += t * dx;
        y += t * dy;
        
        if (fabs(x - round(x)) < 1e-9 && fabs(y - round(y)) < 1e-9) {
            x = round(x);
            y = round(y);
            if (fabs(x - 0) < 1e-9 && fabs(y - p) < 1e-9) return 2;
            if (fabs(x - p) < 1e-9 && fabs(y - p) < 1e-9) return 1;
            if (fabs(x - p) < 1e-9 && fabs(y - 0) < 1e-9) return 0;
        }
        
        if (fabs(t - t_x) < 1e-9) dx = -dx;
        if (fabs(t - t_y) < 1e-9) dy = -dy;
    }
    
    return 0;
}

int main() {
    int p, q;
    scanf("%d %d", &p, &q);
    printf("%d\n", solution(p, q));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(p+q)

May need to simulate up to LCM(p,q)/(p*q) reflections

✓ Linear Growth

Space Complexity

O(1)

Only storing current position and direction

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler