Leetcode 858: Mirror Reflection
In a special square room with mirrors on all four walls, except for the southwest corner, there are receptors at three other corners, numbered 0, 1, and 2. A laser ray is fired from the southwest corner and hits the east wall at a certain distance from the 0th receptor. Given the side length of the square room, p, and the distance q from the 0th receptor on the east wall where the laser ray meets, return the number of the receptor the ray hits first after bouncing around the room.
Problem
Approach
Steps
Complexity
Input: You are given two integers: p, the length of the side of the square room, and q, the distance from the southwest corner to where the laser first meets the east wall.
Example: Input: p = 4, q = 2
Constraints:
• 1 <= q <= p <= 1000
Output: The function should return an integer representing the receptor number (0, 1, or 2) where the laser ray first reaches after bouncing off the walls.
Example: Output: 1
Constraints:
Goal: The goal is to determine which receptor the laser ray hits first, considering how it reflects off the walls of the square room.
Steps:
• Step 1: Check the divisibility of both p and q by 2 and repeatedly divide them by 2 until one of them is odd.
• Step 2: Use the formula `1 - p%2 + q%2` to determine the receptor number.
• Step 3: Return the receptor number.
Goal: The input values p and q are guaranteed to follow the constraints and the ray will eventually meet a receptor.
Steps:
• p is the length of the square room's sides.
• q is the distance from the southwest corner to the first point where the ray meets the east wall.
• The test cases are guaranteed so that the ray will meet a receptor eventually.
Assumptions:
• The room is always square.
• The input values p and q are valid and guarantee that the ray will eventually meet a receptor.
• Input: Input: p = 4, q = 2
• Explanation: In this example, the laser first meets the east wall at a distance of 2 from the 0th receptor. After bouncing, the ray reaches receptor 1, as it is reflected back towards the wall.
Approach: To solve the problem efficiently, we utilize a mathematical approach that simplifies the conditions for determining the receptor. By reducing the values of p and q iteratively through division, we arrive at a formula that can quickly calculate the receptor number.
Observations:
• The problem can be reduced by dividing both p and q by 2 when they are even.
• The solution involves manipulating the parity of p and q to deduce which receptor the ray meets.
Steps:
• Step 1: Continuously divide both p and q by 2 while they are even.
• Step 2: Once one of them becomes odd, use the formula `1 - p%2 + q%2` to find the receptor.
• Step 3: Return the receptor number as the result.
Empty Inputs:
• N/A: Inputs are guaranteed to meet the constraints.
Large Inputs:
• For large values of p and q, the solution still works within time limits due to efficient reduction of the values.
Special Values:
• When p equals q and both are odd, the ray will hit receptor 2.
Constraints:
• The values of p and q will always satisfy the input constraints.
int mirrorReflection(int p, int q) {
while( p % 2 == 0 && q % 2 == 0) p >>= 1, q >>= 1;
return 1 - p%2 + q%2;
}
1 : Function Definition
int mirrorReflection(int p, int q) {
The function `mirrorReflection` takes two integers `p` and `q` as input and returns the mirror reflection based on the conditions in the while loop.
2 : While Loop
while( p % 2 == 0 && q % 2 == 0) p >>= 1, q >>= 1;
The `while` loop repeatedly halves both `p` and `q` (using right shift operator) as long as both are even. This effectively reduces the problem size until at least one of them becomes odd.
3 : Return Statement
return 1 - p%2 + q%2;
After exiting the loop, the function returns a value based on the parity of `p` and `q`. It checks if `p` is odd and `q` is odd and returns an appropriate result based on the mirror reflection rules.
Best Case: O(log p), as the values of p and q are halved iteratively until one of them becomes odd.
Average Case: O(log p), due to the iterative halving process.
Worst Case: O(log p), because the division operation continues until one of p or q is odd.
Description:
Best Case: O(1), since no additional space is needed beyond the input values.
Worst Case: O(1), as only a few variables are used to calculate the result.
Description:
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus