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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Movement of Robots

Difficulty: Medium

Problem Description

You are given an array of integers representing the initial coordinates of robots on an infinite number line, and a string indicating the direction of their movement. Each robot moves one unit per second in the specified direction. If two robots collide, they instantly change their directions. The task is to compute the sum of distances between all pairs of robots after a given number of seconds, modulo (10^9 + 7).

Key Insights

  • Each robot moves in a specified direction ('L' for left, 'R' for right) and may change direction upon collision.
  • The distance between any two robots can be computed directly from their positions after the specified time.
  • The final positions of the robots depend on their initial positions and the collective movement specified by the string.
  • Efficient computation is essential given the constraints, particularly when the number of robots can be as high as (10^5) and time can go up to (10^9).

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the positions. Space Complexity: O(n) - for storing the positions of robots.

Solution

To solve this problem, we can follow these steps:

  1. Calculate the final position of each robot after d seconds based on its initial position and direction.
  2. Sort the final positions to facilitate efficient distance calculations.
  3. Use a two-pointer technique or a prefix sum approach to compute the sum of distances between all pairs of robots.
  4. Return the final sum modulo (10^9 + 7).

The key data structure used here is an array to hold the final positions, and sorting is the primary algorithmic approach to facilitate distance calculations.

Code Solutions

def sum_of_distances(nums, s, d):
    MOD = 10**9 + 7
    n = len(nums)
    positions = []

    # Calculate final positions after d seconds
    for i in range(n):
        if s[i] == 'L':
            positions.append(nums[i] - d)
        else:  # s[i] == 'R'
            positions.append(nums[i] + d)

    # Sort the final positions
    positions.sort()
    
    # Calculate the sum of distances
    total_sum = 0
    prefix_sum = 0
    
    for i in range(n):
        total_sum += positions[i] * i - prefix_sum
        total_sum %= MOD
        prefix_sum += positions[i]
        prefix_sum %= MOD
    
    return total_sum

# Example Usage
print(sum_of_distances([-2, 0, 2], "RLL", 3))  # Output: 8
print(sum_of_distances([1, 0], "RL", 2))        # Output: 5
← Back to All Questions