Final Array State After K Multiplication Operations I Easy Topics Companies Hint You are…
- User
Final Array State After K Multiplication Operations I Easy Topics Companies Hint 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. Return an integer array denoting the final state of nums after performing all k operations.
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] Example 2:
Input: nums = [1,2], k = 3, multiplier = 4
Output: [16,8]
Explanation:
Operation Result After operation 1 [4, 2] After operation 2 [4, 8] After operation 3 [16, 8]
Constraints:
1 <= nums.length <= 100 1 <= nums[i] <= 100 1 <= k <= 10 1 <= multiplier <= 5 format : class Solution { public: vector getFinalState(vector& nums, int k, int multiplier) {
}};
- Assistant
To solve the problem of determining the final state of the array after performing
kmultiplication operations, we can follow a straightforward approach:- Iterate
kTimes: For each operation, we need to perform the following steps. - Find the Minimum Element: Identify the smallest element in the array. If there are multiple occurrences of the minimum value, select the one that appears first.
- Replace with Multiplied Value: Replace the identified minimum element with its multiplied value (
x * multiplier). - Repeat: Continue this process
ktimes.
Given the constraints (
1 <= nums.length <= 100,1 <= k <= 10, etc.), a simple iterative approach with a time complexity ofO(k * n)is efficient enough.Below is the implementation in C++:
#include <vector> #include <algorithm> class Solution { public: std::vector<int> getFinalState(std::vector<int>& nums, int k, int multiplier) { for(int op = 0; op < k; ++op){ // Find the minimum value and its first occurrence int min_val = nums[0]; int min_idx = 0; for(int i = 1; i < nums.size(); ++i){ if(nums[i] < min_val){ min_val = nums[i]; min_idx = i; } } // Replace the minimum value with its multiplied value nums[min_idx] = min_val * multiplier; } return nums; } };Explanation:
-
Loop Through Operations:
- We perform a loop that runs
ktimes, representing thekmultiplication operations.
- We perform a loop that runs
-
Finding the Minimum Element:
- Initialize
min_valwith the first element of the array andmin_idxwith index0. - Iterate through the array to find the smallest value. If a smaller value is found, update
min_valandmin_idxaccordingly. - Since we iterate from left to right, the first occurrence of the minimum value is selected.
- Initialize
-
Replacing the Minimum Element:
- Once the minimum element is identified, multiply it by the
multiplierand update the array at that index.
- Once the minimum element is identified, multiply it by the
-
Return the Final Array:
- After completing all
koperations, return the modifiednumsarray.
- After completing all
Example Walkthrough:
Let's walk through Example 1 to see how the code works.
Input:
nums = [2,1,3,5,6] k = 5 multiplier = 2Operations:
-
Operation 1:
- Minimum value is
1at index1. - Replace
1with1 * 2 = 2. - Array becomes
[2, 2, 3, 5, 6].
- Minimum value is
-
Operation 2:
- Minimum value is
2at index0. - Replace
2with2 * 2 = 4. - Array becomes
[4, 2, 3, 5, 6].
- Minimum value is
-
Operation 3:
- Minimum value is
2at index1. - Replace
2with2 * 2 = 4. - Array becomes
[4, 4, 3, 5, 6].
- Minimum value is
-
Operation 4:
- Minimum value is
3at index2. - Replace
3with3 * 2 = 6. - Array becomes
[4, 4, 6, 5, 6].
- Minimum value is
-
Operation 5:
- Minimum value is
4at index0. - Replace
4with4 * 2 = 8. - Array becomes
[8, 4, 6, 5, 6].
- Minimum value is
Final Output:
[8, 4, 6, 5, 6]Testing the Solution:
To ensure our solution works correctly, let's include a simple test case based on Example 1.
#include <iostream> int main(){ Solution sol; std::vector<int> nums = {2,1,3,5,6}; int k = 5; int multiplier = 2; std::vector<int> result = sol.getFinalState(nums, k, multiplier); // Print the result for(auto num : result){ std::cout << num << " "; } // Expected Output: 8 4 6 5 6 return 0; }Output:
8 4 6 5 6This confirms that our solution works as expected.
- Iterate