We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Movement of Robots

Number: 2787

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given initial positions of robots on an infinite number line (in the array nums) and a corresponding direction for each robot (a string s where 'R' indicates a movement to the right and 'L' to the left), all robots move 1 unit per second. When two robots collide (i.e. share the same position at the same moment) they instantly swap directions. Compute the sum of distances between all pairs of robots after d seconds. As the answer can be huge, return it modulo 10^9 + 7.

Key Insights

  • When two identical robots collide and swap directions the overall set of final positions is the same as if the robots had moved uninterrupted.
  • A robot moving right ends up at (initial position + d), and one moving left ends up at (initial position – d).
  • Once the final positions are calculated, sorting the positions enables us to efficiently compute pairwise distances using a prefix sum technique.
  • The distance sum for a sorted list can be computed incrementally by using the formula: for each index i, contribution = (position[i] * i - prefix_sum_of_previous_positions).

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n)

Solution

We first convert each robot’s movement into a final position by adding or subtracting d from its initial coordinate based on the given direction. Due to the swapping at collisions, the final set of positions is equivalent to these computed positions from a collision-free simulation. The next step is sorting these final positions. With the sorted positions, compute the sum of pairwise distances by iterating through the list and, for each robot, calculating its distance contribution relative to all robots preceding it. This is efficiently done by maintaining a running prefix sum and using modular arithmetic to avoid overflow issues.

Code Solutions

MOD = 10**9 + 7  # modulo constant

def movement_of_robots(nums, s, d):
    n = len(nums)
    final_positions = []
    
    # Compute the final positions based on the direction
    for i in range(n):
        if s[i] == 'R':
            final_positions.append(nums[i] + d)
        else:
            final_positions.append(nums[i] - d)
    
    # Sort the positions to ease pairwise distance calculation
    final_positions.sort()
    
    total_distance = 0
    prefix_sum = 0
    
    # For a sorted array, the distance contribution of each element
    # is given by (position * index - prefix_sum of preceding positions)
    for i in range(n):
        total_distance = (total_distance + (final_positions[i] * i - prefix_sum) % MOD) % MOD
        prefix_sum = (prefix_sum + final_positions[i]) % MOD
        
    return total_distance

# Example usage:
print(movement_of_robots([-2,0,2], "RLL", 3))  # Expected output: 8
print(movement_of_robots([1,0], "RL", 2))        # Expected output: 5
← Back to All Questions