Hi,
If you are located at the bottom left corner (0, 0) of a plane with H x W cells, and you move U positions up and R positions right in each step, how to calculate if you will eventually arrive to a specific cell after any amount of steps? (If you fall to the right of the plane, you get to the left of the plane. Same with falling up)
Thanks.
Hi,
At first i would like to simplify the problem so that we can travel upwards and sideways independently, meaning i can just travel R units in right direction without having to travel upwards.
Now, in order to check if we can arrive at a specific cell, we need to first calculate the minimum displacement we can achieve in both x & y axis (right and up). And if the required cell is located at a multiple of this displacement in the respective axis, we can very well arrive at that cell.
So, how do we calculate the min. displacement in say x axis??
Simple.Find the closet multiple of R greater than W, say it is M. Now M-W is our current location if we were to travel M units in x axis.So the point is, we have achieved a displacement of M-W, which is smaller than R.Continue this same process with our new step size being M-W until W comes out to be a multiple of the new step size.Now this value of step size is our actual minimum displacement which we can traverse in x axis.
Repeat the same for y axis.
Now getting back to the original problem, calculate the minimum no. of steps required to arrive at the given point for both x & y axis independently. The LCM of these two numbers is the number of steps required to arrive at the given point.