C++ में बिंदुओं तक पहुंच (Reaching Points)

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

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

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

• जब tx > sx और ty > sy, करें -
  • यदि tx > ty, तो -
    • tx := tx mod ty
  • अन्यथा
    • ty := ty mod tx
• वापस करें (true जब sx, tx के समान है AND sy <= ty AND (ty - sy) mod tx, 0 के समान है) OR (sy, ty के समान है AND tx >= sx AND (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