I got this question on a coding interview.
Hanna moves in a lattice where every point can be represented by a pair of integers. She moves from point A to point B and then takes a turn 90 degrees right and starts moving till she reaches the first point on the lattice. Find what’s the point she would reach? In essence the problem boils down to finding the first point where the perpendicular to a line will intersect. How do we solve this?
Write the eqation of the perpendicular line.
It will be something of the form ax + by + c = 0
You need to find integer solutions (x,y) which satisfy the above equation. Such equations, where we only care about integer solutions are called Diophantine Equations. The problem is your case is a linear Diophantine Equation. The equation has integer solutions iff gcd(a,b) divides c. In that case, the solutions can be easily computed using the Extended Euclidean Algorithm.
Read the required algorithm here.
In your case, you have to also ensure that the found solution is the closest solution to right of B. This is easy because once you find a solution, all other solutions have this particular form.
Reply if you need any more help