Win After Last Round - Microsoft Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums) {
    // Protect vs empty vector
    if (nums.empty()) return 0;

    // Sort the array to make the rest of the code easier.
    sort(nums.begin(), nums.end());
    const int n = nums.size();

    // We need to find which final score will give us the winning score. This is done by adding the
    // smallest possible points to the best previous scores. We start by adding 1 point to the best
    // score.
    int best = nums[n - 1] + 1;
    // Keep adding more points to swimmers from the best to the worst and check if they have the new
    // max score.
    for (int i = n - 2; i >= 0; --i) {
        best = max<int>(best, nums[i] + (n - i));
    }

    // All we need to do now is to go from the smallest score, add max possible points and check if
    // it beats the winning score.
    for (int i = 0; i < n; ++i) {
        if (nums[i] + n >= best) return n - i;
    }

    return 1;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        int N = nums.length;
        Arrays.sort(nums);
        int best = 0; // minimum score of the winner
        for (int i = 0; i < N; i++) best = Math.max(best, nums[i] + (N - i));
        int ans = 0;
        for (int i = 0; i < N; i++) {
            if (nums[i] + N >= best)
                ans++;
        }
        return ans;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums):
        nums.sort(reverse=True)
        try:
            cut = max(num + i for i, num in enumerate(nums, 1))
        except ValueError:
            return 0
        for i, num in enumerate(nums):
            if num + len(nums) < cut:
                return i
        return len(nums)