3266. Final Array State After K Multiplication Operations II - Solved Code along with explanation

3266. Final Array State After K Multiplication Operations II

In this Problem we will be using a priority queue and a trick, to reduce the complexity. 

The task is simply to return an array (vector) that contains the final state of all the Numbers after performing all k Number of operations and then applying the Modulo.

First, we are passing the 'nums' vector by reference, so we are not creating a copy of the 'nums' vector but we are actually using the 'nums' vector, and making the desired changes, which is faster. 

that's why the use of '&'.

We do the operation using a simple for loop but then we do the operation

Let's say we have k = 11, and multiplier = 2

when k = 1, [5,2,6,5,6]

when k = 2, [5,4,6,5,6]

when k = 3, [5,8,6,5,6]

when k = 4, [10,8,6,5,6]

when k = 5, [10,8,6,10,6]

when k = 6, [10,8,12,10,6]

when k = 7, [10,8,12,10,12] - State achieved! 

initially we have a smallest number '2' in the nums array [5,2,6,5,6], and we keep on doing the operation on this element, until it is not the smallest. 

After the third operation, (k =3), '2' becomes '8' and is no longer the smallest.

At the fourth operation(k=4), we shift to the next smallest number i.e '5' at index 0. We take this five and then multiply it by the multiplier, 5*2 = 10.

Next, at the fifth operation (k=5) We do this with the other '5' at index 3.

Then at ( k = 6 ) We do it with '6' at index 2. 

Then we do this with the second '6' at index 4. Finally attaining a state where each number in the array nums has been Multiplied by the multiplier, at least once ( in this case multiplier = 2) after 7 operations.

Giving us an array state [10,8,12,10,12].

We come to a state, where even if we use the smallest possible multiplier(i.e 2), with the smallest number S, then S*2 will become the biggest, and will not become the smallest until we have iterated over all the remaining elements and multiplied them by 2.

Proof . Say element at index 1 is S. so S = 8.

[10,8,12,10,12]

[10,16,12,10,12]

[20,16,12,10,12]

[20,16,12,20,12]

[20,16,24,20,12]

[20,16,24,20,24] -- all elements iterated, 

Only after iterating over the entire array does S become the smallest again.

Coming back to the example, after only 7 operations, ( k = 7 ) we achieved the state [10,8,12,10,12]. but k = 11. 

So we still have 11 - 7 = 4 operations left, And now since we know that the smallest number will not be the smallest until we multiply all the elements by the multiplier one more time, instead of looking at the priority queue, and trying to find out the smallest number, we would just distribute the operations evenly among all the elements.

so this means 

[10 -> 1 operation , 8 -> 1 operation, 12 -> 1 operation, 10 -> 1 operation, 12] 

giving us a the FINAL state of [20, 16, 24, 20, 12]

    const long long mod = 1000000007;
    class Solution {
    public:
        long long power_mod(long long base, long long exp, long long mod) {
            long long result = 1;
            
            while (exp > 0) {
                if (exp % 2 == 1) {
                    result = (result * base) % mod;
                }
                base = (base * base) % mod;
                exp = exp / 2;
            }
            // this function multiplies a number by itself n times in O(logn)
            return result;
        }
        vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
            if (multiplier == 1) return nums; // do not miss this!!
            priority_queue <pair<long long,long long>, vector<pair<long long,long long>>, greater<pair<long long,long long>>> pq;
            int n = nums.size();
            for (int i = 0; i < n; i++) pq.push({nums[i],i});
            unordered_map<int,int> m,m1;
            // m for storing number of operations at each index
            //m1 to know if all elements have got an operation
            while (1){
                if ((int)m1.size() == n || k == 0) break; // no more operations or state achieved
                long long x = pq.top().first, y = pq.top().second;
                pq.pop();
                x *= multiplier; pq.push({x,y});
                m1[y]++; k--;
            }
            vector<long long> v(n); // to avoid integer overflow
            // This vector will store the elements after ideal state is achieved
            while (!pq.empty()){
                long long x = pq.top().first, y = pq.top().second;
                v[y] = x;
                pq.pop();
            }
            int rep = k/n, md = k%n;
            for (int i = 0; i < n; i++) pq.push({v[i],i});
            while (!pq.empty()){
                int x = pq.top().second;
                m[x] = rep;
                if (md > 0)m[x]++,md--;
                // index x has been assigned its number of operations
                pq.pop();
            }
            // Now just compute every value while calling power_mod funtion
            for (int i = 0; i < n; i++){
                long long mlt = power_mod(multiplier, m[i],mod);
                v[i] = ((v[i]%mod)*(mlt%mod))%mod;
                nums[i] = v[i];
            }
            return nums;
        }
    };