Algorithm of 10041 - Vito's Family

Problem Description Link

This problem you can solve easily .follow this stapes

           1.       Sort the input array of street number.

           2.       Determine the median of array.

               If no. of street is even then mid value are two . so  median is avg of two mid value. If                            no. of   street is odd then mid value is one . so median is that mid value.

                  i.e. 2 6 4 8 9 so median=4; and 2 4 6 8 7 3 so median=(6+8)/2;

           3.       Determine the distance from median to all other values   .

           4.       Sum of all distance is result.

            You need time O(nlogn + n) for this algorithm .

Some input and outputs.

Input:

3

3 2 6 9

5 12 5 6 20 25

6 9 8 7 1 2 4

Output :

7

34

17