Sum Robot Distances After Motion and Collisions
Company: OYO
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Sum Robot Distances After Motion and Collisions
Robots start at the coordinates in a 0-indexed integer array `nums` on an infinite number line. When commanded to move, each robot travels one unit of distance per second. String `s` gives the corresponding initial directions: `'L'` moves left toward negative coordinates, and `'R'` moves right toward positive coordinates.
When two robots occupy the same position at the same moment, they collide and instantly reverse their directions without losing time. Return the sum of distances between every unordered pair of robots after `d` seconds, modulo `10^9 + 7`.
Count `(i, j)` and `(j, i)` as the same pair. Robots starting at `0` and `2` and moving toward each other both reach `1` after one second, reverse immediately, and reach `0` and `2` after the next second. Collisions also occur between integer seconds: robots starting at `0` and `1` moving toward each other meet after half a second; after one second they are back at `0` and `1`, moving away from each other.
### Examples
**Example 1**
```text
Input: nums = [-4,0,3], s = "RLR", d = 2
Output: 14
```
At time `2`, the first two robots meet at `-2`, while the third is at `5`. The three pair distances are `0`, `7`, and `7`, giving `14`. Their instantaneous reversal at that moment does not change these positions.
**Example 2**
```text
Input: nums = [0,3], s = "RL", d = 3
Output: 3
```
The robots meet at coordinate `1.5` after `1.5` seconds and reverse. At time `3`, they are at `0` and `3`, so their distance is `3`.
### Constraints
- `2 <= nums.length <= 10^5`.
- `-2 * 10^9 <= nums[i] <= 2 * 10^9`.
- `0 <= d <= 10^9`.
- `nums.length == s.length`.
- `s` contains only `'L'` and `'R'`.
- The starting coordinates `nums[i]` are unique.
### Clarifying Questions
- Are robot labels relevant to the returned sum? Count every unordered pair; the sum does not identify individual robots.
- Do robots wait after a collision? No; direction changes are instantaneous.
- Can robots share a position at the requested time? Yes; that pair's distance is zero at the collision instant.
- Can `d` be zero? Yes; then use the initial positions.
- Is `nums` already sorted? No ordering is promised; directions correspond to its original indices.
### C++ Interface
```cpp
class Solution {
public:
int sumDistance(vector<int>& nums, string s, int d) {
}
};
```
### Reasoning Checkpoints
- Separate facts that depend on robot identities from facts that depend only on positions.
- Account for fractional collision times without rounding or discrete simulation.
- Bound coordinates, intermediate arithmetic, and the accumulated pair sum separately.
```hint Indistinguishable robots
At a collision, compare reversing two equal-speed robots with letting them pass through while exchanging their labels. Which set of occupied positions would an observer see?
```
Overview: Find the sum of unordered pair distances after equal-speed robots move and reverse instantly on collision, returning the result modulo one billion and seven.