Final Array State After K Multiplication Operations II

Final Array State After K Multiplication Operations II - 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.

After the k operations, apply modulo 10⁹ + 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.

Input & Output

Example 1 — Basic Operations

$ 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, [2,2,3,5,6]. Operation 2: min=2 at index 0, [4,2,3,5,6]. Operation 3: min=2 at index 1, [4,4,3,5,6]. Operation 4: min=3 at index 2, [4,4,6,5,6]. Operation 5: min=4 at index 0, [8,4,6,5,6].

Example 2 — Small Array

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

› Output: [16,8]

💡 Note: Operation 1: min=1 at index 0, [4,2]. Operation 2: min=2 at index 1, [4,8]. Operation 3: min=4 at index 0, [16,8].

Example 3 — Large Values with Modulo

$ Input: nums = [100000,2000], k = 2, multiplier = 1000000

› Output: [999999307,999999993]

💡 Note: After operations array becomes very large, modulo 10^9+7 is applied: [100000000000, 2000000000] → [999999307, 999999993]

Constraints

1 ≤ nums.length ≤ 10⁴
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 10⁹
1 ≤ multiplier ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Initial Array

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

Find & Multiply

Repeatedly find minimum, multiply by 2

Apply Modulo

Final result with modulo 10^9+7 applied

Key Takeaway

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

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is to efficiently find minimum elements repeatedly. The brute force approach scans the array O(n) times for each operation, while the heap approach uses a priority queue to find minimums in O(log n). Best approach is heap-based with Time: O(k log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n * k)	O(1)	Find minimum element k times by scanning entire array
Min-Heap Optimization	O(n log n + k log n)	O(n)	Use priority queue to efficiently find and update minimum elements

Brute Force Simulation — Algorithm Steps

Repeat k times: scan array to find minimum
Multiply the first minimum occurrence
Apply modulo 10^9 + 7 to all elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Min

Scan entire array to find minimum value

Multiply

Multiply first occurrence of minimum

Repeat

Continue until k operations done

Code -

solution.c — C

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

int* solution(int* nums, int numsSize, int k, int multiplier, int* returnSize) {
    const int MOD = 1000000007;
    *returnSize = numsSize;
    
    for (int i = 0; i < k; i++) {
        // Find minimum value and its first index
        int minVal = nums[0];
        int minIdx = 0;
        for (int j = 1; j < numsSize; j++) {
            if (nums[j] < minVal) {
                minVal = nums[j];
                minIdx = j;
            }
        }
        
        // Multiply the minimum value
        nums[minIdx] = ((long long)nums[minIdx] * multiplier) % MOD;
    }
    
    // Apply modulo to all elements
    for (int i = 0; i < numsSize; i++) {
        nums[i] %= MOD;
    }
    
    return nums;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n * k)

For each of k operations, we scan n elements to find minimum

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

3.2K Views

Medium Frequency

~25 min Avg. Time

89 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 Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler