<p>You are given a <strong>0-indexed</strong> array of positive integers <code>w</code> where <code>w[i]</code> describes the <strong>weight</strong> of the <code>i<sup>th</sup></code> index.</p>

<p>You need to implement the function <code>pickIndex()</code>, which <strong>randomly</strong> picks an index in the range <code>[0, w.length - 1]</code> (<strong>inclusive</strong>) and returns it. The <strong>probability</strong> of picking an index <code>i</code> is <code>w[i] / sum(w)</code>.</p>

<ul>
	<li>For example, if <code>w = [1, 3]</code>, the probability of picking index <code>0</code> is <code>1 / (1 + 3) = 0.25</code> (i.e., <code>25%</code>), and the probability of picking index <code>1</code> is <code>3 / (1 + 3) = 0.75</code> (i.e., <code>75%</code>).</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input</strong>
[&quot;Solution&quot;,&quot;pickIndex&quot;]
[[[1]],[]]
<strong>Output</strong>
[null,0]

<strong>Explanation</strong>
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input</strong>
[&quot;Solution&quot;,&quot;pickIndex&quot;,&quot;pickIndex&quot;,&quot;pickIndex&quot;,&quot;pickIndex&quot;,&quot;pickIndex&quot;]
[[[1,3]],[],[],[],[],[]]
<strong>Output</strong>
[null,1,1,1,1,0]

<strong>Explanation</strong>
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= w.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= w[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>pickIndex</code> will be called at most <code>10<sup>4</sup></code> times.</li>
</ul>

class Solution {
public:
    Solution(vector<int>& w) : gen(std::chrono::system_clock::now().time_since_epoch().count()), dis(0,w.size()-1) {
        num_curr_calls = 0;
        max_num_calls = 0;
        last_selected_index = -1;
        index_count_vec = vector<int>(w.size(), 0);
        for (const int elem: w)     max_num_calls += elem;
        const int factor = (max_num_calls > 100000) ? 100000 : 1000;
        if (max_num_calls <= factor)   orig_w = std::move(w);
        else {
            orig_w = vector<int>(w.size(), 0);
            int new_max_num_calls = 0;
            for (int i=0; i<w.size(); ++i) {
                orig_w[i] = (w[i]/static_cast<double>(max_num_calls)) * factor;
                new_max_num_calls += orig_w[i];
            }
            max_num_calls = new_max_num_calls;
        }
    }
    
    int pickIndex() {
        if (num_curr_calls == max_num_calls) {
            num_curr_calls = 0;
            index_count_vec = vector<int>(orig_w.size(), 0);
        }

        ++num_curr_calls;
        int random_index = dis(gen);
        while (index_count_vec[random_index] == orig_w[random_index]) random_index = dis(gen);
        ++index_count_vec[random_index];
        
        return random_index;
    }

private:
    int num_curr_calls;
    int max_num_calls;
    int last_selected_index;
    vector<int> index_count_vec;
    vector<int> orig_w;
    
    std::mt19937 gen;
    std::uniform_int_distribution<> dis;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */
45800