मान लीजिए एक जंगल में, प्रत्येक खरगोश का कुछ रंग होता है। अब खरगोशों का कुछ सबसेट (संभवतः सभी) हमें बताएंगे कि कितने अन्य खरगोशों का वही रंग है जो उनका है। उन उत्तरों को एक सरणी में रखा जाता है। हमें जंगल में हो सकने वाले खरगोशों की न्यूनतम संख्या ढूंढनी है। तो यदि इनपुट [1,1,2] जैसा है, तो आउटपुट 5 होगा, क्योंकि जिन दो खरगोशों ने "1" का उत्तर दिया वे दोनों एक ही रंग के हो सकते हैं, मान लीजिए सफेद। अब जिस खरगोश ने "2" का उत्तर दिया वह सफेद नहीं हो सकता या उत्तर असंगत होंगे। मान लीजिए जिस खरगोश ने "2" का उत्तर दिया वह काला था। तो जंगल में 2 अन्य काले खरगोश होने चाहिए जिन्होंने सरणी में उत्तर नहीं दिया। तो जंगल में खरगोशों की न्यूनतम संभावित संख्या इसलिए 5 है: 3 जिन्होंने उत्तर दिया और 2 जिन्होंने नहीं दिया।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक मैप m बनाएं, और n := ans सरणी का आकार
- ret को 0 पर सेट करें
- i को 0 से n - 1 की रेंज में
- x := ans[i]
- यदि x = 0 है, तो ret को 1 से बढ़ाएं, और इस पुनरावृत्ति के अगले भाग को छोड़ दें।
- यदि m में x है, तो ret को (x + 1) से बढ़ाएं, m[x] := 0 सेट करें
- अन्यथा
- m[x] को 1 से बढ़ाएं
- यदि m[x] = x है, तो m से x को हटा दें
- ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numRabbits(vector<int>& ans) {
map <int, int> m;
int n = ans.size();
int ret = 0;
for(int i = 0; i < n; i++){
int x = ans[i];
if(x == 0){
ret++;
continue;
}
if(!m.count(x)){
ret += (x + 1);
m[x] = 0;
}else{
m[x]++;
if(m[x] == x){
m.erase(x);
}
}
}
return ret;
}
};
main(){
vector<int> v = {1,1,2};
Solution ob;
cout << (ob.numRabbits(v));
}
इनपुट
[1,1,2]
आउटपुट
5
