सी++ में जंगल में खरगोश

मान लीजिए किसी जंगल में हरेक खरगोश का कोई न कोई रंग होता है। अब खरगोशों के कुछ उपसमुच्चय (संभवतः उनमें से सभी) हमें बताएंगे कि कितने अन्य खरगोशों का रंग उनके जैसा ही है। उन उत्तरों को एक सरणी में रखा गया है। हमें जंगल में खरगोशों की न्यूनतम संख्या ज्ञात करनी होगी। इसलिए यदि इनपुट [1,1,2] जैसा है, तो आउटपुट 5 होगा, क्योंकि दो खरगोशों ने "1" का उत्तर दिया, जो दोनों एक ही रंग के हो सकते हैं, जैसे कि सफेद। अब उत्तर "2" से खरगोश सफेद नहीं हो सकता है या उत्तर असंगत होंगे। कहो खरगोश जिसने "2" का उत्तर दिया वह काला था। फिर जंगल में 2 अन्य काले खरगोश होने चाहिए जिन्होंने सरणी में जवाब नहीं दिया। इसलिए जंगल में खरगोशों की सबसे छोटी संभव संख्या 5:3 है जिसका उत्तर प्लस 2 है जो नहीं है।

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

• मानचित्र बनाएं m, और n :=सरणी का आकार ans
• रेट को 0 के रूप में सेट करें
• मैं के लिए 0 से n - 1 की सीमा में
  • x :=ans[i]
  • यदि x =0 है, तो रिट को 1 से बढ़ाएँ और इस पुनरावृत्ति के अगले भाग को छोड़ दें।
  • यदि m में x है, तो ret को (x + 1) से बढ़ाएँ, m[x] सेट करें:=0
  • अन्यथा
    • m[x] को 1 से बढ़ाएं
    • अगर m[x] =x, तो x को m से हटा दें
• रिटर्न रिटर्न

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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