Help with math related problem


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)



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.

1 Like