How to Compute the Shortest Distance on a Circular Road Efficiently

Problem Description

There is a circular road with n stations. The distance between station i and station i+1 (clockwise) is given for all i, and the distance from station n back to station 1 is also provided. Given a start station x and a destination station y, compute the minimal travel distance.

Input

First line: integer n (1 ≤ n ≤ 10⁵).

Second line: n positive integers a_i – clockwise distances between station i and station i+1; the last integer is the distance from station n to station 1.

Third line: two integers x and y (1 ≤ x, y ≤ n) – start and destination stations.

Output

A single integer representing the minimal distance from x to y.

Examples

Example 1

3
1 2 2
2 3

Output:

2

Example 2

3
1 2 2
1 3

Output:

2

Solution Idea

The problem is equivalent to finding the shorter of the two possible routes on a circular path: clockwise from x to y and counter‑clockwise from x to y . Compute the sum of distances for both routes and return the smaller value. Modular arithmetic or simple index wrapping can handle the transition from station n back to station 1 .

Reference Implementations

Python

# Input reading
n = int(input())
distance = list(map(int, input().split()))
x, y = map(int, input().split())
# Convert to 0‑based indices and ensure x < y
x, y = (x-1, y-1) if x < y else (y-1, x-1)
clockwise = sum(distance[x:y])
counter = sum(distance[:x]) + sum(distance[y:])
print(min(clockwise, counter))

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] distances = new int[n];
        for (int i = 0; i < n; i++) {
            distances[i] = scanner.nextInt();
        }
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int clockwise = 0;
        int counter = 0;
        // clockwise distance
        for (int i = x - 1; i != y - 1; i = (i + 1) % n) {
            clockwise += distances[i];
        }
        // counter‑clockwise distance
        for (int i = y - 1; i != x - 1; i = (i + 1) % n) {
            counter += distances[i];
        }
        System.out.println(Math.min(clockwise, counter));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> distance(n);
    for (int i = 0; i < n; ++i) cin >> distance[i];
    int x, y;
    cin >> x >> y;
    if (x > y) swap(x, y);
    long long sumClockwise = 0, sumCounter = 0;
    for (int i = x - 1; i < y - 1; ++i) sumClockwise += distance[i];
    for (int i = 0; i < x - 1; ++i) sumCounter += distance[i];
    for (int i = y - 1; i < n; ++i) sumCounter += distance[i];
    cout << min(sumClockwise, sumCounter) << endl;
    return 0;
}

Complexity Analysis

Time complexity: O(n) – a single traversal of the distance array is sufficient.

Space complexity: O(1) – only a few integer variables are used in addition to the input array.