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.

Examples

Example 1

1
2

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

Example 2

1
2

Input: a = 4, b = 4, c = 6
Output: 7

Example 3

1
2

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

Method 1 – Greedy (Always Take from Largest Piles)

Intuition

At each step, to maximize the score, always remove stones from the two largest non-empty piles. The process stops when at most one pile is non-empty. The answer is the minimum of (a + b + c) // 2 and a + b + c - max(a, b, c).

Approach

  1. Sort the three piles.
  2. If the largest pile is greater than the sum of the other two, the answer is the sum of the two smaller piles.
  3. Otherwise, the answer is (a + b + c) // 2.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int maximumScore(int a, int b, int c) {
        vector<int> v = {a, b, c};
        sort(v.begin(), v.end());
        if (v[2] >= v[0] + v[1]) return v[0] + v[1];
        return (a + b + c) / 2;
    }
};
1
2
3
4
5
6
7
8

func maximumScore(a, b, c int) int {
    v := []int{a, b, c}
    sort.Ints(v)
    if v[2] >= v[0]+v[1] {
        return v[0] + v[1]
    }
    return (a + b + c) / 2
}
1
2
3
4
5
6
7
8

class Solution {
    public int maximumScore(int a, int b, int c) {
        int[] v = {a, b, c};
        Arrays.sort(v);
        if (v[2] >= v[0] + v[1]) return v[0] + v[1];
        return (a + b + c) / 2;
    }
}
1
2
3
4
5
6

class Solution {
    fun maximumScore(a: Int, b: Int, c: Int): Int {
        val v = listOf(a, b, c).sorted()
        return if (v[2] >= v[0] + v[1]) v[0] + v[1] else (a + b + c) / 2
    }
}
1
2
3
4
5
6

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        v = sorted([a, b, c])
        if v[2] >= v[0] + v[1]:
            return v[0] + v[1]
        return (a + b + c) // 2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn maximum_score(a: i32, b: i32, c: i32) -> i32 {
        let mut v = vec![a, b, c];
        v.sort();
        if v[2] >= v[0] + v[1] {
            v[0] + v[1]
        } else {
            (a + b + c) / 2
        }
    }
}
1
2
3
4
5
6
7

class Solution {
    maximumScore(a: number, b: number, c: number): number {
        const v = [a, b, c].sort((x, y) => x - y);
        if (v[2] >= v[0] + v[1]) return v[0] + v[1];
        return Math.floor((a + b + c) / 2);
    }
}

Complexity

  • ⏰ Time complexity: O(1), only a few arithmetic and sort operations on three elements.
  • 🧺 Space complexity: O(1), only a few variables are used.