Solution :

The obvious way is to go with a DFS or BFS like approach. Starting from the point (sx, sy), we can go in two possible directions (sx + sy, sy) and (sx, sx + sy) and then each of these points can go in two possible directions and so on. Note that the paths will form a tree like structure as we are going in either right or upward direction, so we will never encounter the same point twice along a path.

Following method uses DFS with recursion to obtain the solution.

class Solution(object): def reachingPoints(self, sx, sy, tx, ty): if (sx, sy) == (tx, ty): return True elif sx > tx or sy > ty: return False else: return self.reachingPoints(sx + sy, sy, tx, ty) or self.reachingPoints(sx, sy + sy, tx, ty)

We stop whenever we have reached the target (True) or else we have overshoot the target (False).

We can define the time complexity relation to be :

, with if or

which is exponential time complexity .

Given that the range of the points sx, sy, tx and ty is in , it is quite obvious that the above approach will throw "maximum recursion depth reached" or the online judge will throw "Time limit exceeded".

Observe that we can reach a point (tx, ty) from only one point, i.e. if tx >= ty, then we can jump from (tx - ty, ty) to (tx, ty) else if tx < ty, then we can jump from (tx, ty - tx) to (tx, ty).

Thus instead of going from (sx, sy) to (tx, ty), if we go from (tx, ty) to (sx, sy) then we will reach in linear time.

class Solution(object): def reachingPoints(self, sx, sy, tx, ty): if (sx, sy) == (tx, ty): return True elif sx > tx or sy > ty: return False else: if tx >= ty: return self.reachingPoints(sx, sy, tx - ty, ty) else: return self.reachingPoints(sx, sy, tx, ty - tx)

The time complexity is now .

Still the worst case complexity is linear, which means if (sx, sy) = (1, 1) and (tx, ty) = (1000000000, 1), then we would need to cover 1000000000 points even if we know that we will reach (sx, sy) for sure.

To handle the above drawback, instead of jumping only ty from tx or tx from ty in one step, how much can we jump and to what point, so that we can still reach (sx, sy) without overshooting it ?

Let's call this the 'jump_factor'.

for and

for

The modified code is :

class Solution(object): def reachingPoints(self, sx, sy, tx, ty): if (sx, sy) == (tx, ty): return True elif sx > tx or sy > ty: return False else: if tx >= ty: jump_factor = max(int((tx - sx) / ty), 1) return self.reachingPoints(sx, sy, tx - jump_factor * ty, ty) else: jump_factor = max(int((ty - sy) / tx), 1) return self.reachingPoints(sx, sy, tx, ty - jump_factor * tx)

Note that the jump factor cannot be 0, else we would be stuck in one place, hence that 'max' factor.

Categories: PROGRAMMING

Tags: algorithms, BFS, DFS, Leetcode, problem solving, reach points