## PROBLEM LINK :

**Author:** Bharathkumar Hegde

**Tester:** Amogh Aithal

**Editorialist:** Bharathkumar Hegde

## DIFFICULTY:

Cake Walk

## PROBLEM:

```
There will be useful things scattered in row of 10<sup>5</sup> boxes, a bot has to move all the useful things to a single box in minimum number of moves.
```

## QUICK EXPLANATION:

```
Sort the useful positions and find sum of the distances from all useful positions to an useful position which is <strong>(n/2)<sup>th</sup></strong> useful position.
```

## EXPLANATION:

```
First sort all the given useful positions. Let the positions be <strong>a<sub>1</sub> < a<sub>2</sub> < a<sub>3</sub> < .... < a<sub>n</sub></strong>. Let position
<strong>a<sub>opt</sub></strong> be the position to which all useful things are to be moved in minimum number of moves. Therefore minimum moves required is
```

min_moves = (a_{opt}- a_{1}) + (a_{opt}- a_{2}) + .... (useful positions on left of a_{opt}) + (a_{opt}- a_{opt}) + .... + (a_{n-1}- a_{opt}) + (a_{n}- a_{opt}) (useful positions on right of a_{opt})

```
From the above equation it is quite clear that, if we balance the number of useful positions in right and left of a<sub>opt</sub> we can obtain the
minimum number of moves to collect all useful things in a<sub>opt</sub>. Hence if <strong>a<sub>opt</sub> = a<sub>n/2</sub></strong> then it is possible to obtain minimum number of moves.
```