2231C.md (2533B)
1 Source: https://codeforces.com/problemset/problem/2231/C 2 3 C. Chipmunk Theo and Equality 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 While exploring the depths of the Internet, Theodore the chipmunk found a very interesting sequence of positive integers and decided to play with it. 22 23 In one operation, he chooses an element of the sequence and performs the following action: 24 25 * If the chosen element is even, he divides it by 2. 26 * If the chosen element is odd, he increases it by 1. 27 28 Theo really loves equality, so he wants to make all numbers in the sequence equal (otherwise, some numbers might feel offended). Since he needs to plan his lunch time, help him determine the minimum number of operations required to make all numbers equal. 29 30 Input 31 32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 33 34 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the sequence. 35 36 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the sequence. 37 38 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 39 40 Output 41 42 For each test case, output a single integer — the minimum number of operations Theo needs to make all numbers in the sequence equal. 43 44 Example 45 46 Input 47 48 ``` 49 5 50 51 3 52 53 3 2 4 54 55 7 56 57 3 6 7 16 8 8 7 58 59 3 60 61 1 4 2 62 63 5 64 65 10 10 10 10 10 66 67 6 68 69 1 1 3 1 1 1 70 ``` 71 72 Output 73 74 ``` 75 3 76 77 11 78 79 2 80 81 0 82 83 3 84 ``` 85 86 Note 87 88 In the first test case, we have a sequence: $[3, 2, 4]$ 89 90 One possible sequence of operations: $$ [\textbf{3}, 2, 4] \rightarrow [\textbf{4}, 2, 4] \rightarrow [2, 2, \textbf{4}] \rightarrow [2, 2, 2] $$ (Operations are performed on numbers shown in bold.) 91 92 In the second test case, the sequence is: $[3, 6, 7, 16, 8, 8, 7]$ 93 94 Possible operations: 95 96 * Perform the operation once on the 1st element: $3 \rightarrow 4$ 97 * Perform the operation twice on the 2nd element: $6 \rightarrow 3 \rightarrow 4$ 98 * Perform the operation twice on the 4th element: $7 \rightarrow 8 \rightarrow 4$ 99 * Perform the operation twice on the 5th element: $16 \rightarrow 8 \rightarrow 4$ 100 * Perform the operation once on the 6th element: $8 \rightarrow 4$ 101 * Perform the operation once on the 7th element: $8 \rightarrow 4$ 102 * Perform the operation twice on the 8th element: $7 \rightarrow 8 \rightarrow 4$ 103 104 After these $11$ operations, all elements become $4$.