Maximum Score From Removing Stones - Practice Coding Problems

Maximum Score From Removing Stones - Problem

You are playing a solitaire game with three piles of stones of sizes a, b, and c respectively.

Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).

Given three integers a, b, and c, return the maximum score you can get.

Input & Output

Example 1 — Balanced Case

$ Input: a = 2, b = 4, c = 6

› Output: 6

💡 Note: We can take stones from different piles: (6,4), (5,3), (4,2), (3,2), (2,1), (1,1) → 6 moves total

Example 2 — Unbalanced Case

$ Input: a = 4, b = 4, c = 6

› Output: 7

💡 Note: Total = 14, so max possible is 7. Two smaller piles sum to 8, so we can achieve 7 points

Example 3 — Large Pile Dominates

$ Input: a = 1, b = 8, c = 8

› Output: 8

💡 Note: Limited by sum of two smaller piles: min(17/2, 1+8) = min(8, 9) = 8

Constraints

1 ≤ a, b, c ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Three piles with stones: a, b, c

Process

Each turn: pick 2 different non-empty piles, take 1 stone from each, +1 score

Output

Maximum possible score when game ends

Key Takeaway

🎯 Key Insight: Maximum score is limited by either total stones÷2 or sum of two smaller piles

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that maximum score is limited by either total stones divided by 2 (when piles are balanced) or the sum of two smaller piles (when one pile dominates). Best approach uses mathematical formula for O(1) solution. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with Priority Queue	O(n log n)	O(1)	Simulate the game by always picking from two largest piles using a heap
Mathematical Formula	O(1)	O(1)	Use mathematical insight to calculate maximum score directly without simulation
Greedy Strategy	O(n)	O(1)	Always pick stones from the two largest piles to balance them optimally

Simulation with Priority Queue — Algorithm Steps

Put all three pile sizes in a max heap
While at least 2 piles are non-empty, take from two largest
Increment score and update heap
Return total score

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Put all pile sizes in max heap

Take Stones

Always pick from two largest piles

Update

Put remaining stones back and repeat

Code -

solution.c — C

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

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest])
        largest = left;
    
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

int extractMax(int arr[], int* n) {
    if (*n <= 0) return 0;
    int max = arr[0];
    arr[0] = arr[*n - 1];
    (*n)--;
    heapify(arr, *n, 0);
    return max;
}

void insertHeap(int arr[], int* n, int val) {
    if (val <= 0) return;
    arr[*n] = val;
    int i = *n;
    (*n)++;
    
    while (i > 0 && arr[(i-1)/2] < arr[i]) {
        int temp = arr[i];
        arr[i] = arr[(i-1)/2];
        arr[(i-1)/2] = temp;
        i = (i-1)/2;
    }
}

int solution(int a, int b, int c) {
    int heap[10];
    int size = 0;
    
    insertHeap(heap, &size, a);
    insertHeap(heap, &size, b);
    insertHeap(heap, &size, c);
    
    int score = 0;
    
    while (size >= 2) {
        int first = extractMax(heap, &size);
        int second = extractMax(heap, &size);
        
        if (second == 0) break;
        
        score++;
        insertHeap(heap, &size, first - 1);
        insertHeap(heap, &size, second - 1);
    }
    
    return score;
}

int main() {
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    int result = solution(a, b, c);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Each move requires heap operations, and we make at most (a+b+c)/2 moves

⚡ Linearithmic

Space Complexity

O(1)

Only uses a small fixed-size heap for three elements

✓ Linear Space

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

Simulation with Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler