Problem - High-Speed Police Chase

Problem

Coder Raco is working on a police chase problem.

A group of thieves robs a bank and quickly escapes in a car from a location X1 meters away from the city center, traveling at V1 meters per second. A police post, situated X2 meters from the city center, receives the alert, and the officers immediately set off in pursuit at V2 meters per second.

Given that the bank is at position X1, Raco needs to determine whether the police can catch the thieves.

Input: X1:200, V1:80, X2:100, V2:120
Output: true The police are 100 meters behind the thieves and are chasing them at a speed 40 m/s faster. At this rate, they will catch up in 2.5 seconds.

Another example:

Input: X1:150, V1:120, X2:50, V2:100
Output: false

Since the police vehicle is moving slower than the thieves, they will never be able to catch up.

Let’s help by writing the code! 🚔💨

Solution Approach

Linear Motion Problem

Here Raco takes a straightforward approach using the basic formula of time, speed, and distance.

Hint

1. Calculate distance & relative speed.
2. If the time is positive, the police can catch the thieves; otherwise, they cannot.

Algorithm

• Input variables with values x1, x2, v1, v2.
• Calculate the initial distance between the police and the thieves (x1-x2).
• Calculate the relative speed(v2-v1).
• Check if relative speed <= 0 then Output: False
• Else If Calculate the time = distance(step2)/relative speed(step3). – Check if time is positive then return true. – Else return false.
• End

MainLoop	Inner Loop

Code Examples (C)

Linear Motion

// Function to check if police can catch the thieves
_Bool canCatchThieves(int x1, int v1, int x2, int v2) {
    if (v1 == v2) {
        return x1 == x2; // If speeds are equal, they must start at the same position
    }

    double time = (double)(x2 - x1) / (v1 - v2);
    // Police can catch thieves if time is positive and a whole number
    return (time > 0);
}

Complexity

Time Complexity O(1)

Since it is a constant-time calculations, meaning the number of operations does not depend on the input size so O(1) complexity.

Space Complexity O(1)

A constant space is required to store variables, so the space complexity is O(1).