Kevin and Sticks
Tag(s):

## Greedy, Math, Medium

Problem
Editorial
Analytics

Kevin has $n$ sticks. i-th stick has length $a_i$.

Kevin wants every stick has the same length. To achieve his goal he can perform one of the following operation in one second:

• Increase length of one stick by 1.
• Reduce the length of one stick. If the stick has length L, the new length will be $\lfloor {L \over 2} \rfloor$.

Your task is to help Kevin and say the minimum number of seconds to make all sticks have equal length.

Input format:

The first line of input will contain an integer t, denoting the number of test cases.
Each test case starts with the integer n. The next line contains n space-separated integers ai.

Output format:

For every test case output the minimum number of seconds Kevin need to achieve his goal.

Constraints:

• $1 \le t \le 10$
• $1 \le n \le 1000, 1 \le a_i \le 1000$ in 20% of the test cases.
• $1 \le n \le 1000, 1 \le a_i \le 10^9$ in 40% of the test cases.
• $1 \le n \le 10^5, 1 \le a_i \le 10^9$ in 40% of the test cases.
SAMPLE INPUT
1
4
7 4 3 9
SAMPLE OUTPUT
4
Explanation

Sequence of operations:
1) Break first stick. New length will be 3.
2) Increase length of the first stick. New length will be 4.
3) Increase length of the third stick. New length will be 4.
4) Break the last stick. New length will be 4.

Time Limit: 7.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

August Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Probablity
• Math > Basic Geometry