Remove Stones to Minimize the Total - Practice Coding Problems

Remove Stones to Minimize the Total - Problem

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:

Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the largest integer that is smaller than or equal to x (i.e., rounds x down).

Input & Output

Example 1 — Basic Case

$ Input: piles = [5,4,9], k = 2

› Output: 12

💡 Note: Operation 1: Remove floor(9/2) = 4 stones from pile with 9 stones, leaving [5,4,5]. Operation 2: Remove floor(5/2) = 2 stones from any pile with 5 stones, leaving [5,2,5] or [3,4,5]. Total remaining = 12.

Example 2 — Single Operation

$ Input: piles = [4,3,6,7], k = 1

› Output: 17

💡 Note: Remove floor(7/2) = 3 stones from the largest pile (7), leaving [4,3,6,4]. Total remaining = 4 + 3 + 6 + 4 = 17.

Example 3 — Multiple Operations on Same Pile

$ Input: piles = [20], k = 3

› Output: 7

💡 Note: Operation 1: 20 → 10 (remove 10). Operation 2: 10 → 5 (remove 5). Operation 3: 5 → 3 (remove 2). Final result = 7.

Constraints

1 ≤ piles.length ≤ 10⁵
1 ≤ piles[i] ≤ 10⁴
1 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stone piles and k operations to perform

Process

Always remove floor(max_pile/2) stones from largest pile

Output

Sum of remaining stones after k operations

Key Takeaway

🎯 Key Insight: Always removing stones from the largest pile maximizes the total reduction

Asked in

a Amazon 45 G Google 38 M Microsoft 32 f Facebook 28

The key insight is to always remove stones from the largest pile to maximize reduction. Best approach uses a max heap for O(log n) operations. Time: O(n + k log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Max Heap (Optimal)	O(n + k log n)	O(n)	Use a max heap to efficiently track and operate on the largest pile
Brute Force - Try All Combinations	O(n^k)	O(k)	Try every possible sequence of k operations on different piles
Greedy with Sorting	O(k * n log n)	O(1)	Always apply operation on the currently largest pile by sorting after each operation

Max Heap (Optimal) — Algorithm Steps

Build a max heap from all piles
For each of k operations:
Extract maximum pile
Apply operation (remove floor(pile/2) stones)
Reinsert the reduced pile back into heap

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Heap

Create max heap from input piles

Extract & Modify

Pop max, apply operation, push back

Repeat k Times

Continue until all operations complete

Code -

solution.c — C

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

typedef struct {
    int* data;
    int size;
    int capacity;
} MaxHeap;

MaxHeap* createHeap(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) {
    if (idx == 0) return;
    int parent = (idx - 1) / 2;
    if (heap->data[idx] > heap->data[parent]) {
        int temp = heap->data[idx];
        heap->data[idx] = heap->data[parent];
        heap->data[parent] = temp;
        heapifyUp(heap, parent);
    }
}

void heapifyDown(MaxHeap* heap, int idx) {
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    int largest = idx;
    
    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) {
        int temp = heap->data[idx];
        heap->data[idx] = heap->data[largest];
        heap->data[largest] = temp;
        heapifyDown(heap, largest);
    }
}

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

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

int solution(int* piles, int n, int k) {
    MaxHeap* heap = createHeap(n);
    for (int i = 0; i < n; i++) {
        push(heap, piles[i]);
    }
    
    for (int i = 0; i < k; i++) {
        int largest = pop(heap);
        int removed = largest / 2;
        int remaining = largest - removed;
        push(heap, remaining);
    }
    
    int total = 0;
    while (heap->size > 0) {
        total += pop(heap);
    }
    
    free(heap->data);
    free(heap);
    return total;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n + k log n)

Building heap takes O(n), and k operations each take O(log n) for extract/insert

⚡ Linearithmic

Space Complexity

O(n)

Heap stores all n elements

⚡ Linearithmic Space

89.5K Views

Medium Frequency

~15 min Avg. Time

2.8K 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

Max Heap (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler