Odd GCD solution codechef

For Solution
Click Here!
You are given an array A1,A2,…,ANA1,A2,…,AN consisting of NN integers. Your goal is to make the GCD of all the elements in the array an odd integer. To achieve this goal, you can do the following operation any number of times: Odd GCD solution codechef
 Choose an index i(1≤i≤N)i(1≤i≤N) such that Ai>1Ai>1 and set Ai=⌊Ai2 ⌋Ai=⌊Ai2 ⌋
You can choose an index multiple times during the operations. Find the minimum number of operations after which GCD of all the elements in the array becomes an odd integer.
Note: ⌊x⌋⌊x⌋ : Returns the largest integer that is less than or equal to xx (i.e rounds down to the nearest integer). For example, ⌊1.5⌋=1,⌊2⌋=2,⌊1.5⌋=1,⌊2⌋=2, ⌊72 ⌋⌊72 ⌋ =⌊3.5⌋=⌊3.5⌋ =3=3.
Odd GCD solution codechef
 The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
 The first line of each test case contains a single integer NN.
 The second line contains NN spaceseparated integers A1,A2,…,ANA1,A2,…,AN.
Output Format
For each test case, print a single line containing one integer – the minimum number of operations after which GCD of all the elements in the array becomes an odd integer.
Odd GCD solution codechef
 1≤T≤1031≤T≤103
 1≤N≤1051≤N≤105
 1≤Ai≤1091≤Ai≤109
 Sum of NN over all test cases does not exceed 5⋅1055⋅105
Sample Input 1
3
3
2 3 5
2
4 6
3
4 12 24
Odd GCD solution codechef
0
1
2
Odd GCD solution codechef
Test case 11: The GCD of all integers in the array is already 11, which is odd.
Test case 22: You choose the index i=2i=2 and set A2=⌊62 ⌋=⌊3⌋=3A2=⌊62 ⌋=⌊3⌋=3. So the array becomes [4,3][4,3] and the GCD of 44 and 33 is 11.

For Solution
Click Here!