Reconnaissance 2 · Interview Problem

Back to problems

Codeforces

Easy

Arrays

Math

Reconnaissance 2

Given positions of several points on a line, find the best meeting point that minimizes the total travel distance.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Reconnaissance

gfg

Problem Statement

Problem

You are given the positions of several friends on a straight line. You want to choose a meeting point on that same line so that the sum of distances from all friends to that point is as small as possible.

Your task is to compute this minimum possible total distance.

Notes

Distances are measured using absolute difference on the number line.
The meeting point may be any real or integer position on the line; the minimum total distance is what matters.

Intuition

For points on a line, the best meeting point is at a median position. This problem asks you to evaluate the minimum total travel distance for the given set of positions.

Input Format

The first line contains an integer $n$ — the number of friends.
The second line contains $n$ integers describing their positions on the line.

Output Format

Print one integer: the minimum possible sum of distances to a meeting point.

Constraints

$1 \le n$ is small enough for a straightforward solution.
Positions can be negative, zero, or positive.
Use 64-bit integers if necessary for the sum of distances.

Examples

Sample cases returned by the problem API.

Example 1

Input

5
1 2 3 4 5

Output

Explanation

Choosing meeting point 3 gives distances 2 + 1 + 0 + 1 + 2 = 6.

Example 2

Input

4
-1 2 6 7

Output

Explanation

Any point between 2 and 6 is optimal. One valid choice is 2, giving 0 + 0 + 4 + 5 = 9; however, for integer meeting points the minimum is achieved at 6 as well with 3 + 4 + 0 + 1 = 8. The true minimum over all real points is 9. This illustrates why the median interval matters.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress