Odd GCD solution codechef

Odd GCD solution codechef

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(1iN)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 space-separated 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

  • 1T1031≤T≤103
  • 1N1051≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 51055⋅105

Odd GCD solution codechef

 

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.

Leave a Comment