Maximal Score After Applying K Operations

Maximal Score After Applying K Operations - Problem

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation:

choose an index i such that 0 <= i < nums.length,
increase your score by nums[i], and
replace nums[i] with ceil(nums[i] / 3).

Return the maximum possible score you can attain after applying exactly k operations.

The ceiling function ceil(val) is the least integer greater than or equal to val.

Input & Output

Example 1 — Basic Case

$ Input: nums = [10,10,10,10,10], k = 5

› Output: 50

💡 Note: Pick index 0: score=10, nums=[4,10,10,10,10]. Pick index 1: score=20, nums=[4,4,10,10,10]. Pick index 2: score=30, nums=[4,4,4,10,10]. Pick index 3: score=40, nums=[4,4,4,4,10]. Pick index 4: score=50, nums=[4,4,4,4,4]. Maximum score is 50.

Example 2 — Single Large Element

$ Input: nums = [1,10,3,3,3], k = 3

› Output: 17

💡 Note: Pick 10: score=10, nums=[1,4,3,3,3]. Pick 4: score=14, nums=[1,2,3,3,3]. Pick any 3: score=17, nums=[1,2,1,3,3]. Best strategy is always pick the largest available.

Example 3 — Small Array

$ Input: nums = [5], k = 2

› Output: 7

💡 Note: Pick 5: score=5, nums=[2]. Pick 2: score=7, nums=[1]. Only one element, so must pick from it k times.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 10⁶
1 ≤ k ≤ 2 × 10³

Visualization

Tap to expand

Understanding the Visualization

Input

Array [10,10,10,10,10] with k=5 operations

Process

Each operation: pick max, add to score, reduce by ceil(val/3)

Output

Maximum possible score after exactly k operations

Key Takeaway

🎯 Key Insight: Greedy approach works because larger values contribute more to the score, so we should pick them first before they get reduced

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to always pick the largest available element to maximize the score. The greedy max heap approach efficiently tracks the maximum element in O(log n) time per operation. Time: O(n + k log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Max Heap	O(n + k log n)	O(n)	Always pick the largest available element using a priority queue
Brute Force - Try All Combinations	O(n^k)	O(k)	Generate all possible sequences of k operations and find the maximum score

Greedy with Max Heap — Algorithm Steps

Initialize max heap with all array elements
For k operations: extract max, add to score, update and reinsert
Return total score

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Build max heap from input array [10,10,10,10,10]

Extract Max

Pop largest element, add to score, update value

Reinsert

Push updated value back to maintain heap property

Code -

solution.c — C

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

// Simple max heap implementation
typedef struct {
    int* data;
    int size;
    int capacity;
} MaxHeap;

MaxHeap* createMaxHeap(int capacity) {
    MaxHeap* heap = (MaxHeap*)malloc(sizeof(MaxHeap));
    heap->data = (int*)malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

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

void heapifyDown(MaxHeap* heap, int idx) {
    while (1) {
        int largest = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < heap->size && heap->data[left] > heap->data[largest])
            largest = left;
        if (right < heap->size && heap->data[right] > heap->data[largest])
            largest = right;
        
        if (largest == idx) break;
        
        int temp = heap->data[idx];
        heap->data[idx] = heap->data[largest];
        heap->data[largest] = temp;
        
        idx = largest;
    }
}

void push(MaxHeap* heap, int val) {
    heap->data[heap->size] = val;
    heapifyUp(heap, heap->size);
    heap->size++;
}

int pop(MaxHeap* heap) {
    int max = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return max;
}

int solution(int* nums, int len, int k) {
    MaxHeap* maxHeap = createMaxHeap(len + k);
    
    // Build initial heap
    for (int i = 0; i < len; i++) {
        push(maxHeap, nums[i]);
    }
    
    int totalScore = 0;
    
    for (int i = 0; i < k; i++) {
        int maxVal = pop(maxHeap);
        totalScore += maxVal;
        
        int newVal = (int)ceil(maxVal / 3.0);
        push(maxHeap, newVal);
    }
    
    free(maxHeap->data);
    free(maxHeap);
    return totalScore;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n + k log n)

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

⚡ Linearithmic

Space Complexity

O(n)

Max heap stores all n elements from the input array

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 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 Max Heap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler