Maximum Product After K Increments - Practice Coding Problems

Maximum Product After K Increments - Problem

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 10⁹ + 7.

Note that you should maximize the product before taking the modulo.

Input & Output

Example 1 — Basic Case

$ Input: nums = [0,4], k = 5

› Output: 20

💡 Note: Increment the first element 5 times: [0,4] → [5,4]. Product = 5 × 4 = 20.

Example 2 — Multiple Small Elements

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

› Output: 216

💡 Note: Increment smallest elements: [6,3,3,2] → [6,3,3,3] → [6,3,4,3]. Product = 6 × 3 × 4 × 3 = 216.

Example 3 — Zero in Array

$ Input: nums = [1,0,1], k = 1

› Output: 1

💡 Note: Increment the zero: [1,0,1] → [1,1,1]. Product = 1 × 1 × 1 = 1.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁶
1 ≤ k ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [0,4] with k=5 increments available

Strategy

Always increment smallest element for maximum product impact

Output

Final array [5,4] gives maximum product of 20

Key Takeaway

🎯 Key Insight: Always increment the smallest numbers first to maximize the multiplicative effect on the final product

Asked in

G Google 12 a Amazon 8 M Microsoft 6 Apple 4

The key insight is to always increment the smallest elements first to maximize product growth. The best approach uses a min-heap to efficiently find and increment the smallest element k times. Time: O(n + k log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Priority Queue	O(n + k log n)	O(n)	Always increment the smallest element using a min-heap for optimal product growth
Frequency Count Optimization	O(n log n + k)	O(n)	Count frequency of each number and distribute increments optimally among frequency groups
Brute Force - Try All Combinations	O(C(n+k-1, k))	O(k)	Try all possible ways to distribute k increments among array elements

Greedy with Priority Queue — Algorithm Steps

Build min-heap from input array
For each of k operations, extract minimum, increment it, and put back
Calculate final product from all elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Min-Heap

Create heap from array elements

Increment Smallest

Pop min, increment, push back k times

Calculate Product

Multiply all final elements

Code -

solution.c — C

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

const int MOD = 1000000007;

void heapifyUp(int* heap, int idx) {
    int parent = (idx - 1) / 2;
    if (parent >= 0 && heap[parent] > heap[idx]) {
        int temp = heap[parent];
        heap[parent] = heap[idx];
        heap[idx] = temp;
        heapifyUp(heap, parent);
    }
}

void heapifyDown(int* heap, int size, int idx) {
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    int smallest = idx;
    
    if (left < size && heap[left] < heap[smallest]) {
        smallest = left;
    }
    if (right < size && heap[right] < heap[smallest]) {
        smallest = right;
    }
    
    if (smallest != idx) {
        int temp = heap[idx];
        heap[idx] = heap[smallest];
        heap[smallest] = temp;
        heapifyDown(heap, size, smallest);
    }
}

int solution(int* nums, int n, int k) {
    int* heap = (int*)malloc(n * sizeof(int));
    memcpy(heap, nums, n * sizeof(int));
    
    // Build min heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapifyDown(heap, n, i);
    }
    
    for (int i = 0; i < k; i++) {
        heap[0]++;
        heapifyDown(heap, n, 0);
    }
    
    long long result = 1;
    for (int i = 0; i < n; i++) {
        result = (result * heap[i]) % MOD;
    }
    
    free(heap);
    return (int)result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + k log n)

Building heap takes O(n), then k operations each taking O(log n) for heap operations

⚡ Linearithmic

Space Complexity

O(n)

Min-heap stores all n elements

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

425 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

Greedy with Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler