मान लीजिए 1000 बाल्टियां हैं, उनमें से एक जहरीली है, बाकी पानी से भरी हैं। वे सभी समान दिखती हैं। यदि एक सूअर जहर पीता है तो वह 15 मिनट के भीतर मर जाएगा। एक घंटे के भीतर जहरीली बाल्टी का पता लगाने के लिए हमें न्यूनतम कितने सूअरों की आवश्यकता होगी?
अब सामान्य मामले पर विचार करें और इसके लिए एक एल्गोरिदम तैयार करें। तो, सामान्य मामला यह है कि यदि n अलग-अलग बाल्टियां हैं और एक सूअर जहर पीने के m मिनट के भीतर मर जाता है, तो p मिनट के भीतर जहरीली बाल्टी का पता लगाने के लिए कितने सूअरों की आवश्यकता होगी? ठीक एक बाल्टी में जहर है।
जब n = 1000, m = 15 और p = 60, तो आउटपुट 5 होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- ret := 0
- जब (minutesToTest / minutesToDie + 1)^ret < buckets, करें -
- (ret को 1 से बढ़ाएं)
- ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; class Solution { public: int poorPigs(int buckets, int minutesToDie, int minutesToTest) { int ret = 0; while(pow((minutesToTest / minutesToDie + 1), ret) < buckets) ret++; return ret; } }; main(){ Solution ob; cout << (ob.poorPigs(1000,15,60)); }इनपुट
1000 15 60
आउटपुट
5
