Mirror Reflection

Medium
1281.

Mirror Reflection

Mirror Reflection is a medium coding problem on math, number theory and geometry, asked in Amazon and Meta interviews.

A square room has mirrors on all four walls and side length p. Three corners hold receptors: 0 at the south-east corner, 1 at the north-east corner and 2 at the north-west corner. The south-west corner has none.

A laser is fired from the south-west corner and first strikes the east wall at height q above receptor 0. It keeps reflecting off the walls until it hits a receptor.

Return the number of the receptor the ray reaches first. (It always reaches one.)

Example 1

Input
p = 2, q = 1
Output
2
Explanation
The ray hits the east wall halfway up, bounces, and reaches the north-west corner.

Example 2

Input
p = 3, q = 1
Output
1

Example 3

Input
p = 3, q = 2
Output
0

Constraints

  • 1 <= q <= p <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} p
 * @param {number} q
 * @return {number}
 */
var mirrorReflection = function(p, q) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Mirror Reflection — Solution in Python, Java & C++

Mirror Reflection solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Mirror Reflection is a medium coding problem on math, number theory and geometry, asked in Amazon and Meta interviews.

  • Difficulty: Medium
  • Topics: Math, Number Theory, Geometry
  • Asked at: Amazon, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A square room has mirrors on all four walls and side length p. Three corners hold receptors: 0 at the south-east corner, 1 at the north-east corner and 2 at the north-west corner. The south-west corner has none.

A laser is fired from the south-west corner and first strikes the east wall at height q above receptor 0. It keeps reflecting off the walls until it hits a receptor.

Return the number of the receptor the ray reaches first. (It always reaches one.)

Example 1

Input: p = 2, q = 1
Output: 2
Explanation: The ray hits the east wall halfway up, bounces, and reaches the north-west corner.

Example 2

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

Example 3

Input: p = 3, q = 2
Output: 0

Constraints

  • 1 <= q <= p <= 1000

Hints for Mirror Reflection

  1. Hint 1

    Instead of reflecting the ray, reflect the room: stack mirrored copies of the square upwards, and the ray becomes a straight line rising q per room width.

  2. Hint 2

    The ray hits a corner when the height it has risen, k*q, is a multiple of p. Take the smallest such k: then k*q = m*p with m = k*q / p.

  3. Hint 3

    The parity of k says east or west wall, and the parity of m says top or bottom. Dividing p and q by 2 while both are even gives the same parities directly.

How to solve Mirror Reflection

Unfold the reflections: the ray travels in a straight line through mirrored copies of the room, and it meets a corner after the least k wall-widths with k*q a multiple of p. Only the parities of k and m = k*q/p matter.

Approach

  1. While p and q are both even, halve both (this does not change where the ray goes).
  2. If p is now even (so q is odd), return 2.
  3. If q is even (so p is odd), return 0.
  4. Otherwise both are odd: return 1.

Why it works

With g = gcd(p, q), the least k with p | k*q is k = p/g, and then m = q/g. Crossing an odd number of widths ends on the east wall and an even number on the west wall; rising an odd number of heights ends at the top and an even number at the bottom (in the unfolded picture each height flips the room). East-bottom is receptor 0, east-top 1, west-top 2; west-bottom is impossible because p/g and q/g cannot both be even. Halving p and q together until one is odd leaves p/g and q/g with the same parities, which is what the steps test.

Complexity

  • Time — O(log p)
  • Space — O(1)

Pitfalls

  • Simulating the bounces with floating-point geometry drifts; integers are enough.
  • Forgetting to reduce by the common factor: p = 4, q = 2 behaves exactly like p = 2, q = 1.
  • Receptor numbering is easy to swap: 0 is south-east, 1 north-east, 2 north-west.

Reference solution

Python

def mirrorReflection(p: int, q: int) -> int:
    while p % 2 == 0 and q % 2 == 0:
        p //= 2
        q //= 2
    if p % 2 == 0:
        return 2
    if q % 2 == 0:
        return 0
    return 1

Java

public static int mirrorReflection(int p, int q) {
    while (p % 2 == 0 && q % 2 == 0) {
        p /= 2;
        q /= 2;
    }
    if (p % 2 == 0) return 2;
    if (q % 2 == 0) return 0;
    return 1;
}

C++

int mirrorReflection(int p, int q) {
    while (p % 2 == 0 && q % 2 == 0) {
        p /= 2;
        q /= 2;
    }
    if (p % 2 == 0) return 2;
    if (q % 2 == 0) return 0;
    return 1;
}

JavaScript

var mirrorReflection = function(p, q) {
    while (p % 2 === 0 && q % 2 === 0) {
        p /= 2;
        q /= 2;
    }
    if (p % 2 === 0) return 2;
    if (q % 2 === 0) return 0;
    return 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue