Welcome to Subscribe On Youtube
3266. Final Array State After K Multiplication Operations II
Description
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
xinnums. If there are multiple occurrences of the minimum value, select the one that appears first. - Replace the selected minimum value
xwithx * 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 <= 1041 <= nums[i] <= 1091 <= k <= 1091 <= multiplier <= 106
Solutions
Solution 1: Priority Queue (Min-Heap) + Simulation
Let the length of the array $\textit{nums}$ be $n$, and the maximum value be $m$.
We first use a priority queue (min-heap) to simulate the operations until we complete $k$ operations or all elements in the heap are greater than or equal to $m$.
At this point, all elements in the array are less than $m \times \textit{multiplier}$. Since $1 \leq m \leq 10^9$ and $1 \leq \textit{multiplier} \leq 10^6$, $m \times \textit{multiplier} \leq 10^{15}$, which is within the range of a 64-bit integer.
Next, each operation will turn the smallest element in the array into the largest element. Therefore, after every $n$ consecutive operations, each element in the array will have undergone exactly one multiplication operation.
Thus, after the simulation, for the remaining $k$ operations, the smallest $k \bmod n$ elements in the array will undergo $\lfloor k / n \rfloor + 1$ multiplication operations, while the other elements will undergo $\lfloor k / n \rfloor$ multiplication operations.
Finally, we multiply each element in the array by the corresponding number of multiplication operations and take the result modulo $10^9 + 7$. This can be calculated using fast exponentiation.
The time complexity is $O(n \times \log n \times \log M + n \times \log k)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$, and $M$ is the maximum value in the array $\textit{nums}$.
-
class Solution { public int[] getFinalState(int[] nums, int k, int multiplier) { if (multiplier == 1) { return nums; } PriorityQueue<long[]> pq = new PriorityQueue<>( (a, b) -> a[0] == b[0] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0])); int n = nums.length; int m = Arrays.stream(nums).max().getAsInt(); for (int i = 0; i < n; ++i) { pq.offer(new long[] {nums[i], i}); } for (; k > 0 && pq.peek()[0] < m; --k) { long[] p = pq.poll(); p[0] *= multiplier; pq.offer(p); } final int mod = (int) 1e9 + 7; for (int i = 0; i < n; ++i) { long[] p = pq.poll(); long x = p[0]; int j = (int) p[1]; nums[j] = (int) ((x % mod) * qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod); } return nums; } private int qpow(long a, long n, long mod) { long ans = 1 % mod; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ans = ans * a % mod; } a = a * a % mod; } return (int) ans; } } -
class Solution { public: vector<int> getFinalState(vector<int>& nums, int k, int multiplier) { if (multiplier == 1) { return nums; } using ll = long long; using pli = pair<ll, int>; auto cmp = [](const pli& a, const pli& b) { if (a.first == b.first) { return a.second > b.second; } return a.first > b.first; }; priority_queue<pli, vector<pli>, decltype(cmp)> pq(cmp); int n = nums.size(); int m = *max_element(nums.begin(), nums.end()); for (int i = 0; i < n; ++i) { pq.emplace(nums[i], i); } while (k > 0 && pq.top().first < m) { auto p = pq.top(); pq.pop(); p.first *= multiplier; pq.emplace(p); --k; } auto qpow = [&](ll a, ll n, ll mod) { ll ans = 1 % mod; a = a % mod; while (n > 0) { if (n & 1) { ans = ans * a % mod; } a = a * a % mod; n >>= 1; } return ans; }; const int mod = 1e9 + 7; for (int i = 0; i < n; ++i) { auto p = pq.top(); pq.pop(); long long x = p.first; int j = p.second; nums[j] = static_cast<int>((x % mod) * qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod); } return nums; } }; -
class Solution: def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]: if multiplier == 1: return nums pq = [(x, i) for i, x in enumerate(nums)] heapify(pq) m = max(nums) while k and pq[0][0] < m: x, i = heappop(pq) heappush(pq, (x * multiplier, i)) k -= 1 n = len(nums) mod = 10**9 + 7 pq.sort() for i, (x, j) in enumerate(pq): nums[j] = x * pow(multiplier, k // n + int(i < k % n), mod) % mod return nums -
func getFinalState(nums []int, k int, multiplier int) []int { if multiplier == 1 { return nums } n := len(nums) pq := make(hp, n) for i, x := range nums { pq[i] = pair{x, i} } heap.Init(&pq) m := slices.Max(nums) for ; k > 0 && pq[0].x < m; k-- { x := pq[0] heap.Pop(&pq) x.x *= multiplier heap.Push(&pq, x) } const mod int = 1e9 + 7 for i := range nums { p := heap.Pop(&pq).(pair) x, j := p.x, p.i power := k / n if i < k%n { power++ } nums[j] = (x % mod) * qpow(multiplier, power, mod) % mod } return nums } func qpow(a, n, mod int) int { ans := 1 % mod a = a % mod for n > 0 { if n&1 == 1 { ans = (ans * a) % mod } a = (a * a) % mod n >>= 1 } return int(ans) } type pair struct{ x, i int } type hp []pair func (h hp) Len() int { return len(h) } func (h hp) Less(i, j int) bool { return h[i].x < h[j].x || h[i].x == h[j].x && h[i].i < h[j].i } func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *hp) Push(x any) { *h = append(*h, x.(pair)) } func (h *hp) Pop() any { a := *h; x := a[len(a)-1]; *h = a[:len(a)-1]; return x }