C++ में पहुंचना बिंदु

मान लीजिए कि हमारे पास एक प्रारंभिक बिंदु (sx, sy), और लक्ष्य बिंदु (tx, ty) है, हमें यह जांचना होगा कि चालों का एक क्रम प्रारंभ बिंदु से अंत बिंदु तक मौजूद है या नहीं। यहां चाल में एक बिंदु (x, y) लेना और इसे या तो (x, x+y) या (x+y, y) में बदलना शामिल है।

तो अगर इनपुट (1, 1) और (4,5) हैं, तो उत्तर सही होगा, ऐसा इसलिए है क्योंकि (1,1) से (2,1), फिर (3,1), फिर (4 ,1), फिर (4,5)।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• जबकि tx> sx और ty> sy, करते हैं −
  • यदि tx> ty, तो −
    • tx :=tx mod ty
  • अन्यथा
    • ty:=ty mod tx
• वापसी (सच है जब sx tx और sy <=ty और (ty - sy) mod tx के समान है 0) या (sy ty और x> =sx और (tx - sx) mod ty के समान है है 0)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool reachingPoints(int sx, int sy, int tx, int ty) {
      while(tx > sx && ty > sy){
         if(tx > ty){
            tx %= ty;
         }else ty %= tx;
      }
      return (sx == tx && sy <= ty && (ty - sy) % tx == 0) || (sy == ty && tx >= sx && (tx - sx) % ty == 0);
   }
};
main(){
   Solution ob;
   cout << (ob.reachingPoints(1,1,4,5));
}

इनपुट

1
1
4
5

आउटपुट

1