SAC '22 Code Challenge 4 P3 - Obligatory Math Problem

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 256M

Problem types

Since Max loves setting lazy problems, he starts fiddling with an array of N numbers, A, and finds a problem:

Given an array, minimize \sum_{i=1}^N |V-A_i|, where V is the minimizing value and |a-b| denotes the absolute difference between a and b.

Can you solve this lazy problem?


Subtask 1 [40%]

1 \le N \le 1\,000

-100 \le A_i \le 100

Subtask 2 [60%]

1 \le N \le 100\,000

-10^9 \le A_i \le 10^9

Input Specification

The first line will contain N, the number of elements in the array.

The second line will contain N space-separated integers, the elements of the array, A_i.

Output Specification

Output the V that minimizes the equation \sum_{i=1}^N |V-A_i|.

Note: If there are multiple solutions, any will be accepted.

Sample Input

-5 4 9 -3 2 20

Sample Output


Note that 2 and 3 would also be valid solutions.


There are no comments at the moment.