3266. Final Array State After K Multiplication Operations II LeetCode Solution
In this guide, you will get 3266. Final Array State After K Multiplication Operations II LeetCode Solution with the best time and space complexity. The solution to Final Array State After K Multiplication Operations II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Final Array State After K Multiplication Operations II solution in C++
- Final Array State After K Multiplication Operations II solution in Java
- Final Array State After K Multiplication Operations II solution in Python
- Additional Resources
Problem Statement of Final Array State After K Multiplication Operations II
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
Complexity Analysis
- Time Complexity: O(\texttt{sort} + k\log n + n\log(k / n))
- Space Complexity: O(n)
3266. Final Array State After K Multiplication Operations II LeetCode Solution in C++
class Solution {
public:
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
if (multiplier == 1)
return nums;
const int n = nums.size();
const int maxNum = ranges::max(nums);
vector<int> ans(n);
using P = pair<int, int>; // (nums[i], i)
priority_queue<P, vector<P>, greater<>> minHeap;
for (int i = 0; i < n; ++i)
minHeap.emplace(nums[i], i);
// Keep multiplying the minimum number as close as possible to the maximum
// number in the array. After that, stop multiplying the minimum number
// because it will be greater than the maximum number in the array and break
// the circularity.
while (k > 0 &&
static_cast<long>(minHeap.top().first) * multiplier <= maxNum) {
const auto [num, i] = minHeap.top();
minHeap.pop();
minHeap.emplace(num * multiplier, i);
--k;
}
vector<pair<int, int>> sortedIndexedNums;
while (!minHeap.empty())
sortedIndexedNums.push_back(minHeap.top()), minHeap.pop();
const int multipliesPerNum = k / n;
const int remainingK = k % n;
// Evenly distribute the remaining multiplications to each number by using
// fast exponentiation.
for (auto& [num, _] : sortedIndexedNums)
num = (num * modPow(multiplier, multipliesPerNum)) % kMod;
// Distribute the remaining multiplications to the minimum `remainingK`
// numbers.
for (int i = 0; i < remainingK; ++i)
sortedIndexedNums[i].first =
(static_cast<long>(sortedIndexedNums[i].first) * multiplier % kMod);
for (const auto& [num, i] : sortedIndexedNums)
ans[i] = num;
return ans;
}
private:
static constexpr int kMod = 1'000'000'007;
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
};
/* code provided by PROGIEZ */3266. Final Array State After K Multiplication Operations II LeetCode Solution in Java
class Solution {
public int[] getFinalState(int[] nums, int k, int multiplier) {
if (multiplier == 1)
return nums;
final int n = nums.length;
final int maxNum = Arrays.stream(nums).max().getAsInt();
int[] ans = new int[n];
// (nums[i], i)
Queue<int[]> minHeap = new PriorityQueue<>(
(a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
for (int i = 0; i < n; ++i)
minHeap.offer(new int[] {nums[i], i});
// Keep multiplying the minimum number as close as possible to the maximum
// number in the array. After that, stop multiplying the minimum number
// because it will be greater than the maximum number in the array and break
// the circularity.
while (k > 0 && (long) minHeap.peek()[0] * multiplier <= maxNum) {
final int num = minHeap.peek()[0];
final int i = minHeap.poll()[1];
minHeap.offer(new int[] {num * multiplier, i});
--k;
}
List<int[]> sortedIndexedNums = new ArrayList<>(minHeap);
Collections.sort(
sortedIndexedNums,
(a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
final int multipliesPerNum = k / n;
final int remainingK = k % n;
// Evenly distribute the remaining multiplications to each number by using
// fast exponentiation.
for (int[] indexedNums : sortedIndexedNums)
indexedNums[0] = (int) ((long) indexedNums[0] * modPow(multiplier, multipliesPerNum) % kMod);
// Distribute the remaining multiplications to the minimum `remainingK`
// numbers.
for (int i = 0; i < remainingK; ++i)
sortedIndexedNums.get(i)[0] = (int) ((long) sortedIndexedNums.get(i)[0] * multiplier % kMod);
for (int[] indexedNums : sortedIndexedNums) {
final int num = indexedNums[0];
final int i = indexedNums[1];
ans[i] = num;
}
return ans;
}
private static final int kMod = 1_000_000_007;
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
}
// code provided by PROGIEZ3266. Final Array State After K Multiplication Operations II LeetCode Solution in Python
class Solution:
def getFinalState(
self,
nums: list[int],
k: int,
multiplier: int
) -> list[int]:
if multiplier == 1:
return nums
kMod = 1_000_000_007
n = len(nums)
maxNum = max(nums)
ans = [0] * n
minHeap = [(num, i) for i, num in enumerate(nums)]
heapq.heapify(minHeap)
# Keep multiplying the minimum number as close as possible to the maximum
# number in the array. After that, stop multiplying the minimum number
# because it will be greater than the maximum number in the array and break
# the circularity.
while k > 0 and minHeap[0][0] * multiplier <= maxNum:
num, i = heapq.heappop(minHeap)
heapq.heappush(minHeap, (num * multiplier, i))
k -= 1
sortedIndexedNums = sorted(minHeap)
multipliesPerNum, remainingK = divmod(k, n)
# Evenly distribute the remaining multiplications to each number by using
# fast exponentiation.
for index, (num, i) in enumerate(sortedIndexedNums):
sortedIndexedNums[index] = (
sortedIndexedNums[index][0] *
pow(multiplier, multipliesPerNum, kMod) % kMod, i)
# Distribute the remaining multiplications to the minimum `remainingK`
# numbers.
for index in range(remainingK):
sortedIndexedNums[index] = (
sortedIndexedNums[index][0] * multiplier % kMod,
sortedIndexedNums[index][1])
for num, i in sortedIndexedNums:
ans[i] = num
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.