1
/*
2
Explanation:
3

4
Let's say at some point we have coordinates as (a,b)
5
if(a>b) then at the previous step coordinate must be (a-b,b)
6
as it can't be (a,b-a) because all the coordinates are positive and for a>b...
7
b-a<0 this continues till the point when a becomes <=b we can run a loop till
8
there but its time taking we can observe that the above phenomeon occurs till it
9
becomes (a%b,b) example : for (50,7) it would have been like this:
10
(50,7)...(43,7)...(36,7)...........(8,7)..(1,7)
11
1 = 50%7
12
By repeating this procedure, after the loop, we have to test if sx == tx or sy
13
== ty. There is still a condition to test. Let see we got sy = ty = 5 and have
14
the following result sx,sy = (16,5) tx,ty = (21,5) now if we run our program
15
then it will stop at (1,5) which is not equal to sx,sy and will return false
16
however during our iteration we will encounter (16,5) infact after the first
17
iteration only but according to our current code it won't detect it so at the
18
end we apply another condition: check if (tx - sx) % ty == 0. In our case, (21 -
19
16) mod 5 = 0 so we can return true.
20
*/
21

22
class Solution {
23
 public:
24
  // METHOD - 1
25
  bool reachingPoints_recursive(int sx, int sy, int tx, int ty) {
26
    if (sx > tx || sy > ty) {
27
      return false;
28
    }
29

30
    if (sx == tx && sy == ty) {
31
      return true;
32
    }
33

34
    bool canReach = reachingPoints_recursive(sx, sx + sy, tx, ty);
35
    if (!canReach) {
36
      canReach = reachingPoints_recursive(sx + sy, sy, tx, ty);
37
    }
38

39
    return canReach;
40
  }
41

42
  // METHOD - 2
43
  bool reachingPoints_internal(int sx, int sy, int tx, int ty) {
44
    if (sx > tx || sy > ty) {
45
      return false;
46
    } else if (sx == tx && sy == ty) {
47
      return true;
48
    }
49

50
    while (tx > sx && ty > sy) {
51
      if (tx > ty) {
52
        // implies previous path to this tx, ty should have to be tx-ty, ty
53
        // and this could continue till either tx < ty i.e difference would be
54
        // tx % ty so instead of doing that repeatedly just go the final point
55
        // where tx would have started before started adding ty to it repeatedly
56
        tx = tx % ty;
57
      } else {
58
        // implies previous path to this tx, ty should have to be (tx, ty-tx)
59
        // and this could continue till either tx > ty i.e difference would be
60
        // tx % ty so instead of doing that repeatedly just go the final point
61
        // where ty would have started before started adding tx to it repeatedly
62
        ty = ty % tx;
63
      }
64
    }
65

66
    if ((tx == sx) && ((ty - sy) % sx == 0)) {
67
      return true;
68
    } else if ((ty == sy) && ((tx - sx) % sy == 0)) {
69
      return true;
70
    }
71

72
    return false;
73
  }
74

75
  bool reachingPoints(int sx, int sy, int tx, int ty) {
76
    // Method-1 : recurssion - will not work for larger numbers as stack will
77
    // use up all the memory return reachingPoints_recursive(sx, sy, tx, ty);
78

79
    // Method-2 : Effecient non recursive solution
80
    return reachingPoints_internal(sx, sy, tx, ty);
81
  }
82
};