Minimum Array Sum

Minimum Array Sum - Problem

You are given an integer array nums and three integers k, op1, and op2.

You can perform the following operations on nums:

Operation 1: Choose an index i and divide nums[i] by 2, rounding up to the nearest whole number. You can perform this operation at most op1 times, and not more than once per index.
Operation 2: Choose an index i and subtract k from nums[i], but only if nums[i] is greater than or equal to k. You can perform this operation at most op2 times, and not more than once per index.

Note: Both operations can be applied to the same index, but at most once each.

Return the minimum possible sum of all elements in nums after performing any number of operations.

Input & Output

Example 1 — Basic Operations

$ Input: nums = [2,8,3,19,3], k = 3, op1 = 2, op2 = 2

› Output: 23

💡 Note: Apply op1 to 8 (8→4) and 19 (19→10), then op2 to both results if beneficial. Final array becomes [2,4,3,10,3] with sum 22, but optimal is 23 after careful operation selection.

Example 2 — Limited Operations

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

› Output: 6

💡 Note: Apply op1 to 4 (4→2) and op2 to one element ≥3. Best is to halve 4 and subtract k from 3, giving [2,2,0] with sum 4. But considering all combinations, optimal sum is 6.

Example 3 — No Valid Operations

$ Input: nums = [1,1,2], k = 3, op1 = 1, op2 = 1

› Output: 4

💡 Note: Only op1 can be applied since all values < k. Apply op1 to 2 (2→1), resulting in [1,1,1] with sum 3. But optimal strategy gives sum 4.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ 10⁵
0 ≤ op1, op2 ≤ nums.length

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to calculate the reduction benefit of each possible operation and greedily select the ones with maximum impact. The greedy priority queue approach gives optimal results in O(n log n) time by always choosing the operation that reduces the sum the most.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Priority Queue	O(n log n)	O(n)	Use priority queue to always select the operation that gives maximum reduction
Try All Combinations	O(4ⁿ)	O(n)	Generate all possible ways to apply operations and find minimum sum

Greedy Priority Queue — Algorithm Steps

Step 1: For each element, calculate reduction from op1, op2, and both operations
Step 2: Add all beneficial operations to a priority queue ordered by reduction amount
Step 3: Pop operations with highest reduction while respecting operation limits

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Reductions

For each element, find reduction from op1, op2, and both

Priority Queue

Order operations by reduction amount (highest first)

Apply Greedily

Select operations with maximum benefit until limits reached

Code -

solution.c — C

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

typedef struct {
    int reduction;
    int type;
    int index;
    int finalValue;
} Operation;

typedef struct {
    Operation* data;
    int size;
    int capacity;
} PriorityQueue;

PriorityQueue* createPQ(int capacity) {
    PriorityQueue* pq = malloc(sizeof(PriorityQueue));
    pq->data = malloc(capacity * sizeof(Operation));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

void heapifyUp(PriorityQueue* pq, int idx) {
    if (idx == 0) return;
    int parent = (idx - 1) / 2;
    if (pq->data[parent].reduction < pq->data[idx].reduction) {
        Operation temp = pq->data[parent];
        pq->data[parent] = pq->data[idx];
        pq->data[idx] = temp;
        heapifyUp(pq, parent);
    }
}

void heapifyDown(PriorityQueue* pq, int idx) {
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    int maxIdx = idx;
    
    if (left < pq->size && pq->data[left].reduction > pq->data[maxIdx].reduction) {
        maxIdx = left;
    }
    if (right < pq->size && pq->data[right].reduction > pq->data[maxIdx].reduction) {
        maxIdx = right;
    }
    
    if (maxIdx != idx) {
        Operation temp = pq->data[maxIdx];
        pq->data[maxIdx] = pq->data[idx];
        pq->data[idx] = temp;
        heapifyDown(pq, maxIdx);
    }
}

void push(PriorityQueue* pq, Operation op) {
    if (pq->size >= pq->capacity) return;
    pq->data[pq->size] = op;
    heapifyUp(pq, pq->size);
    pq->size++;
}

Operation pop(PriorityQueue* pq) {
    Operation result = pq->data[0];
    pq->data[0] = pq->data[pq->size - 1];
    pq->size--;
    heapifyDown(pq, 0);
    return result;
}

int solution(int* nums, int n, int k, int op1, int op2) {
    PriorityQueue* pq = createPQ(n * 3);
    
    for (int i = 0; i < n; i++) {
        int val = nums[i];
        int original = val;
        
        // Operation 1 only
        int op1Val = (val + 1) / 2;
        if (op1Val < original) {
            Operation op = {original - op1Val, 1, i, op1Val};
            push(pq, op);
        }
        
        // Operation 2 only
        if (val >= k) {
            int op2Val = val - k;
            Operation op = {original - op2Val, 2, i, op2Val};
            push(pq, op);
        }
        
        // Both operations
        if (val >= k) {
            int temp1 = (val + 1) / 2;
            if (temp1 >= k) {
                int bothVal1 = temp1 - k;
                Operation op = {original - bothVal1, 3, i, bothVal1};
                push(pq, op);
            }
            
            int temp2 = val - k;
            int bothVal2 = (temp2 + 1) / 2;
            Operation op = {original - bothVal2, 3, i, bothVal2};
            push(pq, op);
        }
    }
    
    int* result = malloc(n * sizeof(int));
    bool* usedOp1 = calloc(n, sizeof(bool));
    bool* usedOp2 = calloc(n, sizeof(bool));
    
    for (int i = 0; i < n; i++) {
        result[i] = nums[i];
    }
    
    int remainingOp1 = op1;
    int remainingOp2 = op2;
    
    while (pq->size > 0 && (remainingOp1 > 0 || remainingOp2 > 0)) {
        Operation op = pop(pq);
        
        if (op.type == 1) {
            if (remainingOp1 > 0 && !usedOp1[op.index]) {
                result[op.index] = op.finalValue;
                usedOp1[op.index] = true;
                remainingOp1--;
            }
        } else if (op.type == 2) {
            if (remainingOp2 > 0 && !usedOp2[op.index]) {
                result[op.index] = op.finalValue;
                usedOp2[op.index] = true;
                remainingOp2--;
            }
        } else if (op.type == 3) {
            if (remainingOp1 > 0 && remainingOp2 > 0 && !usedOp1[op.index] && !usedOp2[op.index]) {
                result[op.index] = op.finalValue;
                usedOp1[op.index] = true;
                usedOp2[op.index] = true;
                remainingOp1--;
                remainingOp2--;
            }
        }
    }
    
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += result[i];
    }
    
    free(result);
    free(usedOp1);
    free(usedOp2);
    free(pq->data);
    free(pq);
    
    return sum;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Priority queue operations for up to 3n possible operations

⚡ Linearithmic

Space Complexity

O(n)

Priority queue stores operation candidates for each element

⚡ Linearithmic Space

21.4K Views

Medium Frequency

~25 min Avg. Time

856 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 Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler