Daily bit(e) of C++ | Swinging movement
Daily bit(e) of C++ #44, The common C++ interview problem: Swinging movement
Today, we will look at a common C++ interview question: Swinging movement.
Given a starting position and a destination (positive integer coordinates), determine whether the destination can be reached using a swinging movement. That is, we can move from a position of {x,y} to either {x+y,y} or {x,x+y}.
Before you continue reading the solution, I recommend you try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/TTshG4Ph3.
Solution
The core observation for this problem is that the "swing" operation is completely reversible. The destination coordinate {x,y} can only be reached from {x-y,y} or {x,y-x}. On top of that, since our coordinates are positive integers, only one of the two directions is possible.
Because of this reversibility, for any destination, there is only one possible backwards path leading from (to) this destination. We can therefore trace this path, checking whether we at any point reach our source coordinate.
This approach, however, has the unfortunate problem of being linear (consider the case of {1,1}→{MAX_INT, 1}).
Fortunately, there is an operation that we can use instead of repeatedly applying the minus operation, the modulo.
However, we need to be careful. Consider the case: {7,15}→{7,29}. If we straightforwardly apply the modulo operation, we can skip over our destination, going from {7,29} directly to {7,1}. Notably, this only happens when one of the coordinates is already correct.
