Problem Brief

Get Minimum Time

FULLTIMEOA

See Amazon online assessment and hiring insights

Developers at Amazon have deployed an application with a distributed database. It is stored on total_servers different servers numbered from 1 to total_servers that are connected in a circular fashion, i.e. 1 is connected to 2, 2 is connected to 3, and so on until total_servers connects back to 1.

There is a subset of servers represented by an array servers of integers. They need to transfer the data to each other to be synchronized. Data transfer from one server to one it is directly connected to takes 1 unit of time. Starting from any server, find the minimum amount of time to transfer the data to all the other servers.

Function Description

Complete the function getMinTime in the editor.

getMinTime takes the following arguments:

int total_servers: The number of servers in the system
int servers[n]: The servers to share the data with

Returns

int: The minimum time required to transfer the data on all the servers

🍊 A million thanks, spike 👍

1Example 1

Input

total_servers = 8, servers = [2, 6, 8]

Output

Explanation

Two possible paths are shown, but there can be many more. One path goes from 2 to 6 to 8 taking 6 units of time. The other path goes from 2 to 8 to 6 and takes 4 units of time. Return the shorter path length, 4.

2Example 2

Input

total_servers = 5, servers = [1, 5]

Output

Explanation

The two servers are directly connected so it will take only 1 unit of time to share the data.

3Example 3

Input

total_servers = 10, servers = [4, 6, 2, 9]

Output

Explanation

An optimal strategy is to start from server 2 and go to 4, then 6, then 9. It takes 2 + 2 + 3 = 7 units of time.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ total_servers ≤ 10⁹
1 ≤ n ≤ 10⁵
1 ≤ servers[i] ≤ n