You are given an integer array nums, an integer k, and an integer multiplier. You need…
- User
You are given an integer array nums, an integer k, and an integer multiplier.
You need to perform k operations on nums. In each operation:
Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first. Replace the selected minimum value x with x * multiplier. After the k operations, apply modulo 109 + 7 to every value in nums.
Return an integer array denoting the final state of nums after performing all k operations and then applying the modulo.
Example 1:
Input: nums = [2,1,3,5,6], k = 5, multiplier = 2
Output: [8,4,6,5,6]
Explanation:
Operation Result After operation 1 [2, 2, 3, 5, 6] After operation 2 [4, 2, 3, 5, 6] After operation 3 [4, 4, 3, 5, 6] After operation 4 [4, 4, 6, 5, 6] After operation 5 [8, 4, 6, 5, 6] After applying modulo [8, 4, 6, 5, 6] Example 2:
Input: nums = [100000,2000], k = 2, multiplier = 1000000
Output: [999999307,999999993]
Explanation:
Operation Result After operation 1 [100000, 2000000000] After operation 2 [100000000000, 2000000000] After applying modulo [999999307, 999999993]
Constraints:
1 <= nums.length <= 104 1 <= nums[i] <= 109 1 <= k <= 109 1 <= multiplier <= 106 give cpp answer in this format : class Solution { public: vector getFinalState(vector& nums, int k, int multiplier) {
}};
- Assistant
#include <vector> #include <queue> #include <cstdint> using namespace std; class Solution { public: // Define the modulo constant const int MOD = 1'000'000'007; // Struct to represent each element in the priority queue struct Element { __int128 value; int index; // Comparator for min-heap: first by value, then by index bool operator<(const Element& other) const { if (value != other.value) { return value > other.value; // Min-heap based on value } return index > other.index; // If values equal, smaller index first } }; // Helper function to find the maximum t such that v0 * m^t <= limit long long find_max_t(__int128 v0, int m, __int128 limit, long long k) { if(m == 1){ if(v0 <= limit){ return k; } else{ return 0; } } if(v0 > limit){ return 0; } long long left = 1; long long right = k; long long ans = 0; while(left <= right){ long long mid = left + (right - left) / 2; __int128 temp = v0; bool valid = true; for(long long t = 0; t < mid; ++t){ if(temp > limit / m){ valid = false; break; } temp *= m; } if(valid && temp <= limit){ ans = mid; left = mid + 1; } else{ right = mid -1; } } return ans; } // Main function to get the final state of the array vector<int> getFinalState(vector<int>& nums, int k, int multiplier) { int n = nums.size(); // Initialize the priority queue with all elements priority_queue<Element> pq; // Use a separate vector to keep track of the latest values vector<__int128> vp(n); for(int i =0; i < n; ++i){ vp[i] = nums[i]; pq.push(Element{vp[i], i}); } // Define a very large value for infinity const __int128 INF = (__int128)1e40; while(k >0 && !pq.empty()){ // Pop the smallest element Element current = pq.top(); pq.pop(); __int128 v0 = current.value; int i0 = current.index; // Determine the next minimal value __int128 next_min = INF; if(!pq.empty()){ next_min = pq.top().value; } // Determine the maximum number of operations t_max long long t_max; if(multiplier ==1){ if(v0 <= next_min){ t_max = k; } else{ t_max =0; } } else{ if(v0 > next_min){ t_max =0; } else{ t_max = find_max_t(v0, multiplier, next_min, k); } } // If no bulk operations can be performed, perform one operation if(t_max ==0){ // Perform one operation __int128 new_val = v0 * multiplier; vp[i0] = new_val; pq.push(Element{new_val, i0}); k -=1; } else{ // Perform t_max operations // Compute v0 * m^t_max safely __int128 new_val = v0; for(long long t =0; t < t_max; ++t){ new_val *= multiplier; } vp[i0] = new_val; pq.push(Element{new_val, i0}); k -= t_max; } } // Prepare the final result by applying modulo vector<int> result(n); for(int i =0; i < n; ++i){ // To handle negative values correctly when using modulo __int128 mod_val = vp[i] % MOD; if(mod_val <0){ mod_val += MOD; } result[i] = (int)mod_val; } return result; } };