Maximum Score From Removing Stones - Leetcode Solution

Problem Statement:

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. Given three integers a, b, and c, return the maximum score you can get.

Example 1:

Input: a = 2, b = 4, c = 6 Output: 6 Explanation: The optimal strategy is to take one from pile c and two from pile b; Score = 1 + 2 = 3. On the second turn, take one from pile c and two from pile a; Score = 2 + 3 = 5. On the third turn, take one from pile b and one from pile a; Score = 3 + 4 = 7. The game ends because there are fewer than two non-empty piles. Overall score = 3 + 5 + 7 = 15.

Example 2:

Input: a = 4, b = 4, c = 6 Output: 7 Explanation: The optimal strategy is to take one from pile a and two from pile c; Score = 1 + 2 = 3. On the second turn, take one from pile a and two from pile b; Score = 2 + 3 = 5. On the third turn, take one from pile c and one from pile b; Score = 3 + 4 = 7. The game ends because there are fewer than two non-empty piles. Overall score = 3 + 5 + 7 = 15.

Solution:

To maximize the score, we need to remove the stones that are in the largest pile and one of the other piles. This is because when we take one stone from the largest pile and a stone from one of the other piles, we get the maximum possible score.

First, we sort the input in non-increasing order to get the largest pile as the first element and then the rest in decreasing order.

We then take the stones from two non-empty piles in a cyclic manner. We keep track of the score and the number of stones left in each pile.

We continue to remove stones until there are fewer than two non-empty piles left. When this happens, we return the maximum score we have obtained so far.

Code:

class Solution { public int maximumScore(int a, int b, int c) {

    int[] arr = new int[]{a,b,c};
    
    Arrays.sort(arr);
    
    int score = 0;
    
    while(arr[1]!=0){
        
        arr[2]--;
        arr[1]--;
        
        score++;
        
        Arrays.sort(arr);
        
    }
    
    return score;
}

}

Time Complexity: O(log n) Space Complexity: O(1)

Explanation of Time complexity:

The time complexity of the above code is O(1) because there is only a fixed number of iterations that occur while taking stones from the piles. This is because, after each move, the array is sorted, and the second-largest and smallest piles are chosen for removal. This ensures that the loop doesn't run for more than two iterations. Therefore, the time complexity of the algorithm is O(1).

1