C++ এ বনে খরগোশ

ধরুন একটি বনে, প্রতিটি খরগোশের কিছু রঙ আছে। এখন খরগোশের কিছু উপসেট (সম্ভবত তাদের সবগুলি) আমাদের বলবে যে কতগুলি অন্যান্য খরগোশের রঙ একই রকম। যারা উত্তর একটি অ্যারে স্থাপন করা হয়. আমাদের খুঁজে বের করতে হবে ন্যূনতম কত খরগোশ বনে থাকতে পারে। সুতরাং যদি ইনপুটটি [1,1,2] এর মত হয়, তাহলে আউটপুট হবে 5, যেমন দুটি খরগোশ যারা "1" উত্তর দিয়েছে যে উভয়ই একই রঙের হতে পারে, বলুন সাদা। এখন "2" উত্তরের চেয়ে খরগোশ সাদা হতে পারে না বা উত্তরগুলি অসামঞ্জস্যপূর্ণ হবে। বলুন যে খরগোশটি "2" উত্তর দিয়েছে তা কালো ছিল। তারপরে বনে 2টি কালো খরগোশ থাকা উচিত যারা অ্যারেতে উত্তর দেয়নি। তাই বনে খরগোশের সংখ্যা সবচেয়ে কম তাই হল 5:3 যেটি উত্তর দিয়েছে প্লাস 2 যা দেয়নি৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র তৈরি করুন m, এবং n :=অ্যারের আকারের ans
• রেট 0 হিসাবে সেট করুন
• আমি 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 মুছে দিন
• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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