Final Array State After K Multiplication Operations I

Final Array State After K Multiplication Operations I - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3,5,6], k = 5, multiplier = 2

› Output: [8,4,6,5,6]

💡 Note: Operation 1: min=1 at index 1, nums becomes [2,2,3,5,6]. Operation 2: min=2 at index 0, nums becomes [4,2,3,5,6]. Operation 3: min=2 at index 1, nums becomes [4,4,3,5,6]. Operation 4: min=3 at index 2, nums becomes [4,4,6,5,6]. Operation 5: min=4 at index 0, nums becomes [8,4,6,5,6].

Example 2 — Single Element

$ Input: nums = [1], k = 3, multiplier = 4

› Output: [64]

💡 Note: Start with [1]. After operation 1: [4]. After operation 2: [16]. After operation 3: [64].

Example 3 — No Operations

$ Input: nums = [3,2,1], k = 0, multiplier = 5

› Output: [3,2,1]

💡 Note: With k=0, no operations are performed, so array remains unchanged.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 100
1 ≤ k ≤ 10
1 ≤ multiplier ≤ 5

Visualization

Tap to expand

Understanding the Visualization

Input Array

nums = [2,1,3,5,6], k=5, multiplier=2

Find & Multiply Min

Repeatedly find minimum and multiply by 2

Final Result

Array after k operations: [8,4,6,5,6]

Key Takeaway

🎯 Key Insight: Use min-heap to efficiently find minimum in O(log n) instead of O(n) linear search

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is efficiently finding the minimum element k times. The brute force approach scans the array linearly for each operation, while the heap approach uses a min-heap for O(log n) minimum extraction. Best approach is the min-heap solution. Time: O(n + k log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Linear Search	O(k×n)	O(1)	For each operation, scan the entire array to find minimum
Min-Heap Priority Queue	O(n + k log n)	O(n)	Use min-heap to efficiently find minimum in O(log n) time

Brute Force Linear Search — Algorithm Steps

Repeat k times:
Find minimum value in array
Find first index of minimum
Multiply that element by multiplier

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Array

Start with nums = [2,1,3,5,6]

Find Min

Scan array to find minimum value and its index

Multiply

Multiply the minimum by multiplier

Repeat

Repeat k times until all operations complete

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* nums, int numsSize, int k, int multiplier) {
    for (int i = 0; i < k; i++) {
        int minVal = nums[0];
        int minIdx = 0;
        for (int j = 1; j < numsSize; j++) {
            if (nums[j] < minVal) {
                minVal = nums[j];
                minIdx = j;
            }
        }
        nums[minIdx] *= multiplier;
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k, multiplier;
    scanf("%d", &k);
    scanf("%d", &multiplier);
    
    solution(nums, numsSize, k, multiplier);
    
    printf("[");
    for (int i = 0; i < numsSize; i++) {
        printf("%d", nums[i]);
        if (i < numsSize - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k×n)

k operations, each requiring O(n) linear search

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra arrays

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler