C++-এ র্যাবিটস ইন ফরেস্ট সমস্যা সমাধান

মান করুন একটি জঙ্গলে প্রতিটি খরগোশের কিছু রঙ রয়েছে। এখন খরগোশের কিছু সাবসেট (হয়তো সবাই) আমাদের বলবে কতগুলো অন্য খরগোশ তাদের মতো রঙের। সেই উত্তরগুলো একটি অ্যারেতে রাখা হয়। আমাদের বের করতে হবে জঙ্গলে কমপক্ষে কতগুলো খরগোশ থাকতে পারে।

যদি ইনপুট হয় [1,1,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]++ করুন
  - যদি 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]