ধরুন আমাদের ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে w আছে, যেখানে w[i] ইনডেক্স i-এর ওজন বর্ণনা করে, আমাদের pickIndex() নামে একটি ফাংশন সংজ্ঞায়িত করতে হবে যা যাদুকরীভাবে একটি ইনডেক্স পিক করে তার ওজন অনুপাতে।
তাই যদি ইনপুট হয় [1,3], pickIndex() পাঁচবার কল করলে, তবে উত্তর আসতে পারে − 0, 1, 1, 1, 0।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- একটি v অ্যারে সংজ্ঞায়িত করুন,
- ইনিশিয়ালাইজারের মাধ্যমে, ইনিশিয়ালাইজ করুন যেন
- n := w[0]
- i = 1 থেকে w-এর আকার পর্যন্ত
- w[i] := w[i] + w[i – 1]
- n := w[i]
- v = w
- pickIndex() নিম্নরূপ কাজ করবে −
- একটি র্যান্ডম সংখ্যা r নিন, r mod v-এর শেষ উপাদান করুন
- v থেকে r-এর চেয়ে ছোট নয় এমন সবচেয়ে ছোট সংখ্যা নিন, তারপর v-এর প্রথম সংখ্যা বিয়োগ করুন এবং ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int n; vector <int> v; Solution(vector<int>& w) { srand(time(NULL)); n = w[0]; for(int i = 1; i < w.size(); i++){ w[i] += w[i - 1]; n = w[i]; } v = w; } int pickIndex() { return upper_bound(v.begin(), v.end(), rand() % v.back()) - v.begin(); } }; main(){ vector<int> v = {1,3}; Solution ob(v); cout << (ob.pickIndex()) << endl; cout << (ob.pickIndex()) << endl; cout << (ob.pickIndex()) << endl; cout << (ob.pickIndex()) << endl; cout << (ob.pickIndex()) << endl; }ইনপুট
[1, 3] দিয়ে ইনিশিয়ালাইজ করুন এবং pickIndex পাঁচবার কল করুন।
আউটপুট
1 1 1 1 0
