We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Mirror Reflection

Number: 888

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

A laser ray is emitted from the southwest corner of a square room with mirrors on all four walls. The ray first meets the east wall at a distance q from the 0th receptor at the southeast corner. The problem asks for the receptor (labeled 0, 1, or 2 at the other three corners) that the ray will hit first, given that the ray eventually meets one of these receptors.

Key Insights

  • The path of the ray can be understood by reflecting the room rather than tracking the reflections.
  • Instead of simulating the reflections, we extend the room into multiple copies, turning the ray's path into a straight line.
  • Let m be the number of room extensions along the vertical direction (each extension being a copy of the room); similarly, let n be the number of extensions along the horizontal direction.
  • The ray will meet a receptor when mp equals np + some multiple? More formally, the ray will eventually hit a receptor when m * q is a multiple of p.
  • Determine m such that m * q % p == 0. Then, let n = (m * q) / p.
  • Based on whether m and n are odd or even, the receptor can be determined:
    • If m is even: receptor 0.
    • If m is odd and n is odd: receptor 1.
    • If m is odd and n is even: receptor 2.

Space and Time Complexity

Time Complexity: O(p) in worst-case scenario since m is incremented until m * q is a multiple of p. Space Complexity: O(1) as only a few integer variables are used.

Solution

The solution uses the mathematical insight that the problem can be reduced to finding the smallest positive integer m such that m * q is a multiple of p. This is achieved using a simple loop. Once m is found, the corresponding n is computed as n = (m * q) / p. The parity (odd or even nature) of m and n determine which receptor is met:

  • Even m indicates an even number of room extensions upward, meaning the path hits receptor 0.
  • If m is odd, it means the ray ultimately travels upward. Then, if n (the horizontal reflections) is odd, the receptor is 1 (northeast corner); if n is even, the receptor is 2 (southeast corner reflected to the west wall). The primary data used are integers, and a loop is used to increment m until the divisibility condition is met.

Code Solutions

# Define the function mirrorReflection with parameters p and q.
def mirrorReflection(p, q):
    # m represents the number of room extensions vertically.
    m = 1  
    # Loop until we find an m such that m * q is divisible by p.
    while (m * q) % p != 0:
        m += 1  # Increment m until the condition is met.
    
    # n represents the number of room extensions horizontally.
    n = (m * q) // p  # Integer division to get the count.
    
    # Check parity to determine the receptor.
    if m % 2 == 0:
        # If m is even, the ray ends at receptor 0.
        return 0
    else:
        if n % 2 == 1:
            # If m is odd and n is odd, the ray hits receptor 1.
            return 1
        else:
            # If m is odd and n is even, the ray hits receptor 2.
            return 2

# Example test cases
print(mirrorReflection(2, 1))  # Expected output: 2
print(mirrorReflection(3, 1))  # Expected output: 1
← Back to All Questions