[Solved] Odd GCD codechef solution – 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 codechef solution

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:

  • 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 codechef solution

Input Format

  • 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 codechef solution

Constraints

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

Sample Input 1 

3
3
2 3 5
2
4 6
3 
4 12 24

Sample Output 1 

0
1 
2

Odd GCD codechef solution

Explanation

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.


  1. Airline Restrictions codechef solution
  2. Travel Pass codechef solution
  3. Shuffling Parities codechef solution
  4. XOR Equal codechef solution
  5. 2-D Point Meeting codechef solution
  6. Minimize Digit Sum codechef solution
  7. Treasure Hunt codechef solution

Odd GCD codechef solution

Leave a Comment