How to Compute the Shortest Distance on a Circular Road Between Two Stations

Problem Statement

Given a circular road with n stations. The clockwise distance from station i to i+1 (and from n to 1) is a_i. For given start station x and destination station y (1‑indexed), compute the minimum travel distance along the circle.

Input

First line: integer n (1 ≤ n ≤ 10^5).

Second line: n positive integers a_i (1 ≤ a_i ≤ 10^9) – clockwise distances.

Third line: two integers x and y (1 ≤ x, y ≤ n).

Output

One integer – the shortest distance between stations x and y.

Solution Overview

The circle provides exactly two possible routes: clockwise from x to y and counter‑clockwise from x to y. Compute the sum of distances for each route and output the smaller sum. Index handling can be simplified by converting to 0‑based indices and using modular arithmetic or by swapping so that x < y.

Algorithm

Read n and the array a.

Read x and y, convert to 0‑based: x--, y--.

If x > y, swap them so that x is the smaller index.

Clockwise distance = sum of a[x..y‑1].

Counter‑clockwise distance = sum of a[0..x‑1] plus sum of a[y..n‑1] (or total sum minus clockwise distance).

Print min(clockwise, counter).

Reference Implementations

Python 3

import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]
    x = int(next(it)) - 1
    y = int(next(it)) - 1

    if x > y:
        x, y = y, x

    clockwise = sum(a[x:y])
    counter = sum(a[:x]) + sum(a[y:])
    print(min(clockwise, counter))

if __name__ == "__main__":
    main()

Java 17

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int x = sc.nextInt() - 1;
        int y = sc.nextInt() - 1;

        if (x > y) {
            int tmp = x;
            x = y;
            y = tmp;
        }

        long clockwise = 0;
        for (int i = x; i < y; i++) {
            clockwise += a[i];
        }

        long counter = 0;
        for (int i = 0; i < x; i++) {
            counter += a[i];
        }
        for (int i = y; i < n; i++) {
            counter += a[i];
        }

        System.out.println(Math.min(clockwise, counter));
    }
}

C++ (GNU‑C++17)

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n)) return 0;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    int x, y;
    std::cin >> x >> y;
    --x; --y;
    if (x > y) std::swap(x, y);

    long long clockwise = 0;
    for (int i = x; i < y; ++i) clockwise += a[i];

    long long counter = 0;
    for (int i = 0; i < x; ++i) counter += a[i];
    for (int i = y; i < n; ++i) counter += a[i];

    std::cout << std::min(clockwise, counter) << '
';
    return 0;
}

Complexity Analysis

Each implementation traverses the distance array at most twice, giving O(n) time. Only a few scalar variables are used in addition to the input array, so the extra memory consumption is O(1) .