Jobs

Interviews

Discussions

Mirror Reflection

Medium

Asked by:

10 views

Topics:

Bit ManipulationGreedy Algorithms

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 0^th 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.

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

Constraints:

1 <= q <= p <= 1000

Try coding it in LeetCode

Mirror Reflection

Medium

Asked by:

10 views

Topics:

Bit ManipulationGreedy Algorithms

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 0^th 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.

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

Constraints:

1 <= q <= p <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are p and q guaranteed to be positive integers?
What is the maximum possible value for p and q?
If the ray never hits a receptor (0 or 1), what value should I return?
Is the corner at (0,0) always considered the starting point, and are the receptors always located at (p,0) and (0,p)?
Can p and q have a common factor greater than 1? If so, how does that affect the calculation?

Brute Force Solution

Approach

We can think of the laser beam as bouncing around a rectangular room until it hits a corner. The brute force way involves tracing the beam's path step by step, calculating each bounce to see where it will hit next. We continue this process until the beam hits one of the corners we're interested in.

Here's how the algorithm would work step-by-step:

Imagine the laser beam starts at the initial point and travels in a straight line.
Calculate where that line intersects with one of the walls of the room.
Determine which wall the beam hit.
Based on the wall that was hit, calculate the new direction of the beam after the bounce (like a mirror reflection).
Repeat steps 2-4, tracing the path of the beam, bounce after bounce.
Keep track of the coordinates of each bounce.
For each bounce, check if it has reached either the top right corner, the bottom right corner, or has exceeded the maximum number of bounces permitted. The maximum number of bounces permitted prevents infinite loops.
If it has reached the top right corner, return 0.
If it has reached the bottom right corner, return 1.
If the beam has hit any other corner or exceeded max bounces, return 2.

Code Implementation

def mirror_reflection_brute_force(room_width, room_height):
    max_bounces = 1000
    current_x = 0
    current_y = 0
    direction_x = 1
    direction_y = 1

    for bounce_count in range(max_bounces):
        # Calculate time to hit a vertical wall
        time_to_vertical = float('inf')
        if direction_x == 1:
            time_to_vertical = (room_width - current_x) 
        elif direction_x == -1:
            time_to_vertical = current_x 

        # Calculate time to hit a horizontal wall
        time_to_horizontal = float('inf')
        if direction_y == 1:
            time_to_horizontal = (room_height - current_y) 
        elif direction_y == -1:
            time_to_horizontal = current_y 

        # Determine which wall is hit first
        if time_to_vertical < time_to_horizontal:
            current_x = current_x + direction_x * time_to_vertical
            current_y = current_y + direction_y * time_to_vertical
            current_y = round(current_y, 5)
            direction_x *= -1
        else:
            current_x = current_x + direction_x * time_to_horizontal
            current_y = current_y + direction_y * time_to_horizontal
            current_x = round(current_x, 5)
            direction_y *= -1

        # Check if we've reached a target corner
        if current_x == room_width and current_y == room_height:
            # Top right corner
            return 1

        if current_x == room_width and current_y == 0:
            # Bottom right corner
            return 0

        if current_x == 0 and current_y == room_height:
            # Some other corner
            return 2

        if current_x == 0 and current_y == 0:
            return 2

    return 2

Big(O) Analysis

Time Complexity

O(k) – The time complexity is determined by the number of bounces, let's denote that as k. In the brute force approach, we trace the laser beam's path step by step, calculating each bounce and checking if it hits a target corner (0 or 1). Each bounce involves calculating the intersection point of a line with the room's walls and updating the direction, which takes constant time. Since we perform these calculations for each bounce until we reach a target corner, an invalid corner, or hit the maximum bounce limit, the total time taken is proportional to the number of bounces, k. Therefore, the time complexity of the brute force algorithm is O(k).

Space Complexity

O(1) – The algorithm described in the plain English explanation primarily involves calculating the path of the laser beam, its reflections, and tracking its coordinates. It mentions keeping track of the coordinates of each bounce, and checking if the beam has reached certain corners or exceeded the maximum number of bounces. However, the number of bounces is capped by 'max bounces'. Since the space needed to store the current coordinates, direction, and a counter for max bounces doesn't depend on the input room size and is bounded, the auxiliary space complexity is constant.

Optimal Solution

Approach

The core idea is to visualize the reflections as extending the room into a grid of rooms. We keep extending these rooms until a corner where the beam hits is aligned with one of the receivers, then we can use math to figure out which receiver was hit.

Here's how the algorithm would work step-by-step:

Imagine the room repeating infinitely in both directions, creating a grid of identical rooms.
The light beam travels in a straight line through this grid.
Keep extending the room dimensions in both directions (horizontally and vertically) until the extended distance equals the point where the beam hits a corner.
Figure out how many times the room was extended horizontally and vertically.
Use the number of horizontal and vertical extensions to determine if the corner the beam hits is receiver 0, 1, or 2.

Code Implementation

def mirror_reflection(room_dimension_p, beam_extension_q):
    horizontal_extension = beam_extension_q
    vertical_extension = 0

    while horizontal_extension % room_dimension_p != 0:
        least_common_multiple = room_dimension_p

        # Extending until the beam hits a corner.
        horizontal_extension += beam_extension_q
        vertical_extension += room_dimension_p

    horizontal_multiple = horizontal_extension // room_dimension_p
    vertical_multiple = vertical_extension // room_dimension_p

    # Check if the number of vertical extensions is odd
    if vertical_multiple % 2 == 1:
        # Check if the number of horizontal extensions is odd
        if horizontal_multiple % 2 == 1:
            return 1
        else:
            return 0
    else:
        #If number of horizontal extension is odd it means it hits receiver 2
        if horizontal_multiple % 2 == 1:
            return 2
        else:
            return -1

Big(O) Analysis

Time Complexity

O(1) – The algorithm extends the room dimensions until the least common multiple (LCM) of p and q is reached. The number of extensions required is directly related to the LCM, which is bounded by p*q. However, we are not iterating over an input of size 'n'. The values p and q are constants defining the room dimensions. Therefore, the number of operations required to find the LCM and perform the calculations remains constant regardless of any variable input size. Thus, the time complexity is O(1).

Space Complexity

O(1) – The plain English explanation describes extending the room dimensions and counting how many times this extension occurs horizontally and vertically. This process uses a constant number of variables to track the extended distances and counts, independent of the input room dimensions (p and q). Therefore, the algorithm uses a constant amount of extra space.

Edge Cases

Case	How to Handle
p or q is zero	Return -1 immediately since the mirror is impossible with a zero-sized room dimension.
p equals q	If p and q are equal, the ray hits receptor 0 if p is divisible by q and 1 otherwise.
Large p and q that lead to potential integer overflow	Use long integer data types for calculations to prevent overflow.
The reflection point is exactly at a corner	Handle this case by directly calculating the number of reflections and checking divisibility to determine the receptor.
p and q are relatively prime large numbers	Ensure efficient calculation of the least common multiple, avoiding redundant computations.
The least common multiple calculations leads to an overflow.	Check for potential overflow during LCM calculation using multiplication with appropriate overflow prevention measures.
p and q are both even	Continuously divide both p and q by 2 until at least one of them is odd to simplify the problem and avoid infinite loops.
The solution requires very large number of reflections before hitting 0, 1 or 2	Optimise the computation of reflections to avoid excessive iterations, potentially utilizing mathematical properties to directly jump to the solution.

p or q is zero

How to Handle:

Return -1 immediately since the mirror is impossible with a zero-sized room dimension.

p equals q

How to Handle:

If p and q are equal, the ray hits receptor 0 if p is divisible by q and 1 otherwise.

Large p and q that lead to potential integer overflow

How to Handle:

Use long integer data types for calculations to prevent overflow.

The reflection point is exactly at a corner

How to Handle:

Handle this case by directly calculating the number of reflections and checking divisibility to determine the receptor.

p and q are relatively prime large numbers

How to Handle:

Ensure efficient calculation of the least common multiple, avoiding redundant computations.

The least common multiple calculations leads to an overflow.

How to Handle:

Check for potential overflow during LCM calculation using multiplication with appropriate overflow prevention measures.

p and q are both even

How to Handle:

Continuously divide both p and q by 2 until at least one of them is odd to simplify the problem and avoid infinite loops.

The solution requires very large number of reflections before hitting 0, 1 or 2

How to Handle:

Optimise the computation of reflections to avoid excessive iterations, potentially utilizing mathematical properties to directly jump to the solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are p and q guaranteed to be positive integers?
What is the maximum possible value for p and q?
If the ray never hits a receptor (0 or 1), what value should I return?
Is the corner at (0,0) always considered the starting point, and are the receptors always located at (p,0) and (0,p)?
Can p and q have a common factor greater than 1? If so, how does that affect the calculation?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the laser beam starts at the initial point and travels in a straight line.
Calculate where that line intersects with one of the walls of the room.
Determine which wall the beam hit.
Based on the wall that was hit, calculate the new direction of the beam after the bounce (like a mirror reflection).
Repeat steps 2-4, tracing the path of the beam, bounce after bounce.
Keep track of the coordinates of each bounce.
For each bounce, check if it has reached either the top right corner, the bottom right corner, or has exceeded the maximum number of bounces permitted. The maximum number of bounces permitted prevents infinite loops.
If it has reached the top right corner, return 0.
If it has reached the bottom right corner, return 1.
If the beam has hit any other corner or exceeded max bounces, return 2.

Code Implementation

def mirror_reflection_brute_force(room_width, room_height):
    max_bounces = 1000
    current_x = 0
    current_y = 0
    direction_x = 1
    direction_y = 1

    for bounce_count in range(max_bounces):
        # Calculate time to hit a vertical wall
        time_to_vertical = float('inf')
        if direction_x == 1:
            time_to_vertical = (room_width - current_x) 
        elif direction_x == -1:
            time_to_vertical = current_x 

        # Calculate time to hit a horizontal wall
        time_to_horizontal = float('inf')
        if direction_y == 1:
            time_to_horizontal = (room_height - current_y) 
        elif direction_y == -1:
            time_to_horizontal = current_y 

        # Determine which wall is hit first
        if time_to_vertical < time_to_horizontal:
            current_x = current_x + direction_x * time_to_vertical
            current_y = current_y + direction_y * time_to_vertical
            current_y = round(current_y, 5)
            direction_x *= -1
        else:
            current_x = current_x + direction_x * time_to_horizontal
            current_y = current_y + direction_y * time_to_horizontal
            current_x = round(current_x, 5)
            direction_y *= -1

        # Check if we've reached a target corner
        if current_x == room_width and current_y == room_height:
            # Top right corner
            return 1

        if current_x == room_width and current_y == 0:
            # Bottom right corner
            return 0

        if current_x == 0 and current_y == room_height:
            # Some other corner
            return 2

        if current_x == 0 and current_y == 0:
            return 2

    return 2

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the room repeating infinitely in both directions, creating a grid of identical rooms.
The light beam travels in a straight line through this grid.
Keep extending the room dimensions in both directions (horizontally and vertically) until the extended distance equals the point where the beam hits a corner.
Figure out how many times the room was extended horizontally and vertically.
Use the number of horizontal and vertical extensions to determine if the corner the beam hits is receiver 0, 1, or 2.

Code Implementation

def mirror_reflection(room_dimension_p, beam_extension_q):
    horizontal_extension = beam_extension_q
    vertical_extension = 0

    while horizontal_extension % room_dimension_p != 0:
        least_common_multiple = room_dimension_p

        # Extending until the beam hits a corner.
        horizontal_extension += beam_extension_q
        vertical_extension += room_dimension_p

    horizontal_multiple = horizontal_extension // room_dimension_p
    vertical_multiple = vertical_extension // room_dimension_p

    # Check if the number of vertical extensions is odd
    if vertical_multiple % 2 == 1:
        # Check if the number of horizontal extensions is odd
        if horizontal_multiple % 2 == 1:
            return 1
        else:
            return 0
    else:
        #If number of horizontal extension is odd it means it hits receiver 2
        if horizontal_multiple % 2 == 1:
            return 2
        else:
            return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
p or q is zero	Return -1 immediately since the mirror is impossible with a zero-sized room dimension.
p equals q	If p and q are equal, the ray hits receptor 0 if p is divisible by q and 1 otherwise.
Large p and q that lead to potential integer overflow	Use long integer data types for calculations to prevent overflow.
The reflection point is exactly at a corner	Handle this case by directly calculating the number of reflections and checking divisibility to determine the receptor.
p and q are relatively prime large numbers	Ensure efficient calculation of the least common multiple, avoiding redundant computations.
The least common multiple calculations leads to an overflow.	Check for potential overflow during LCM calculation using multiplication with appropriate overflow prevention measures.
p and q are both even	Continuously divide both p and q by 2 until at least one of them is odd to simplify the problem and avoid infinite loops.
The solution requires very large number of reflections before hitting 0, 1 or 2	Optimise the computation of reflections to avoid excessive iterations, potentially utilizing mathematical properties to directly jump to the solution.

p or q is zero

How to Handle:

Return -1 immediately since the mirror is impossible with a zero-sized room dimension.

p equals q

How to Handle:

If p and q are equal, the ray hits receptor 0 if p is divisible by q and 1 otherwise.

Large p and q that lead to potential integer overflow

How to Handle:

Use long integer data types for calculations to prevent overflow.

The reflection point is exactly at a corner

How to Handle:

Handle this case by directly calculating the number of reflections and checking divisibility to determine the receptor.

p and q are relatively prime large numbers

How to Handle:

Ensure efficient calculation of the least common multiple, avoiding redundant computations.

The least common multiple calculations leads to an overflow.

How to Handle:

Check for potential overflow during LCM calculation using multiplication with appropriate overflow prevention measures.

p and q are both even

How to Handle:

Continuously divide both p and q by 2 until at least one of them is odd to simplify the problem and avoid infinite loops.

The solution requires very large number of reflections before hitting 0, 1 or 2

How to Handle:

Optimise the computation of reflections to avoid excessive iterations, potentially utilizing mathematical properties to directly jump to the solution.