Compute the Final Robot Score
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given an array `scores`, where `scores[i]` is the score of the `i`-th robot.
Robots repeatedly compete using the following rules:
1. Select the two robots with the highest current scores, `x` and `y`, where `x >= y`.
2. These two robots compete.
3. If `x == y`, both robots are removed.
4. If `x > y`, the robot with score `y` is removed, and the robot with score `x` remains with a new score of `x - y`.
5. Repeat until at most one robot remains.
Return the score of the final remaining robot. If no robots remain, return `0`.
Design and implement an efficient algorithm. Analyze its time and space complexity.
Example:
```text
Input: scores = [2, 7, 4, 1, 8, 1]
Output: 1
```
Explanation:
```text
8 and 7 compete -> remaining score 1, scores become [2, 4, 1, 1, 1]
4 and 2 compete -> remaining score 2, scores become [2, 1, 1, 1]
2 and 1 compete -> remaining score 1, scores become [1, 1, 1]
1 and 1 compete -> both removed, scores become [1]
Final score is 1
```
Quick Answer: This question evaluates data structure and algorithm proficiency, focusing on managing dynamic multisets with priority-based selection and reasoning about iterative reductions and complexity.
You are given an array `scores`, where `scores[i]` is the score of the `i`-th robot. Robots repeatedly compete as follows: choose the two robots with the highest current scores `x` and `y` where `x >= y`. If `x == y`, both robots are removed. If `x > y`, the robot with score `y` is removed and the robot with score `x` stays with a new score of `x - y`. Continue until at most one robot remains. Return the score of the final remaining robot. If no robots remain, return `0`. Your solution should be efficient for large inputs.
Constraints
- 0 <= len(scores) <= 100000
- 0 <= scores[i] <= 1000000000
Examples
Input: ([2,7,4,1,8,1],)
Expected Output: 1
Explanation: The process can go as: 8 and 7 -> 1, then 4 and 2 -> 2, then 2 and 1 -> 1, then 1 and 1 disappear, leaving 1.
Input: ([10],)
Expected Output: 10
Explanation: Only one robot exists, so its score is the final answer.
Input: ([],)
Expected Output: 0
Explanation: No robots are present, so no robot remains.
Input: ([5,5,5,5],)
Expected Output: 0
Explanation: The first two 5s remove each other, and the remaining two 5s also remove each other.
Input: ([9,3,3],)
Expected Output: 3
Explanation: First 9 and 3 compete to make 6, then 6 and 3 compete to make 3.
Hints
- You need to repeatedly access and remove the two largest scores efficiently.
- A priority queue (max-heap) avoids re-sorting the array after every competition.