मान लीजिए 1000 बाल्टी हैं, उनमें से एक जहरीली है, अन्य पानी से भरी हैं। वे सभी एक जैसे दिखते हैं। अगर सुअर जहर पी लेता है तो 15 मिनट के अंदर उसकी मौत हो जाती है। एक घंटे के भीतर जहरीली बाल्टी का पता लगाने के लिए सूअरों की न्यूनतम मात्रा क्या होगी?
तो अब सामान्य मामले पर विचार करें और इसके लिए एक एल्गोरिदम तैयार करें। तो, सामान्य स्थिति यह है कि यदि n अलग-अलग बाल्टी हैं और जहर पीने वाला सुअर m मिनट के भीतर मर जाएगा, तो p मिनट के भीतर जहरीली बाल्टी खोजने के लिए कितने सूअरों की आवश्यकता होगी? जहर के साथ बिल्कुल एक बाल्टी है।
जब n =1000, m =15 और p =60, तब आउटपुट 5 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- रिट:=0
- जबकि (मिनटों का परीक्षण / मिनटटोडी + 1)^रिट <बाल्टी, करते हैं −
- (रिटर्न 1 से बढ़ाएं)
- रिटर्न रिटर्न
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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