मान लीजिए हमारे पास क्षमता x और y लीटर के दो जग हैं। हमारे पास अनंत मात्रा में पानी की आपूर्ति उपलब्ध है। अब हमें यह निर्धारित करना है कि क्या इन दो जगों का उपयोग करके ठीक z लीटर मापना संभव है। यदि z लीटर पानी मापने योग्य है, तो अंत तक एक या दोनों बाल्टियों में z लीटर पानी होना चाहिए।
हम ये कुछ ऑपरेशन कर सकते हैं:
- किसी भी जग को पूरी तरह से पानी से भरें।
- किसी भी जग को खाली करें।
- एक जग से दूसरे जग में पानी डालें जब तक कि दूसरा जग पूरी तरह से भर न जाए या पहला जग स्वयं खाली न हो जाए।
उदाहरण के लिए, यदि x = 2 और y = 5, और z = 4, तो यह true लौटाएगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- यदि
x + y < z, तो गलत लौटाएं - यदि
x = zयाy = z, याx + y = z, तो सही लौटाएं - यदि
z, x और y के gcd से विभाज्य हैतो सही लौटाएं, अन्यथा गलत
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: bool canMeasureWater(int x, int y, int z) { if(x + y < z) return false; if(x == z || y == z || x + y == z) return true; return z % __gcd(x, y) == 0; } }; main(){ Solution ob; cout << (ob.canMeasureWater(3,5,4)); }इनपुट
3 5 4
आउटपुट
1