Odd GCD codechef solution

 

Contest Code:START14B

 

Problem Code:BININVER

You are given an array A1,A2,…,AN$A_1,A_2,\dots ,A_N$ consisting of N$N$ 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(1≤i≤N)$i(1\le i\le N)$ such that Ai>1$A_i>1$ and set Ai=⌊Ai2 ⌋$A_i=\lfloor \frac{A_i}{2}\rfloor$

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⌋$\lfloor x\rfloor$ : Returns the largest integer that is less than or equal to x$x$ (i.e rounds down to the nearest integer). For example, ⌊1.5⌋=1,⌊2⌋=2,$\lfloor 1.5\rfloor =1,\lfloor 2\rfloor =2,$ ⌊72 ⌋$\lfloor \frac{7}{2}\rfloor$ =⌊3.5⌋$=\lfloor 3.5\rfloor$ =3$=3$.

Input Format

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

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.

Constraints

• 1≤T≤103$1\le T\le {10}^3$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤Ai≤109$1\le A_i\le {10}^9$
• Sum of N$N$ over all test cases does not exceed 5⋅105$5\cdot {10}^5$

Sample Input 1 

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

Sample Output 1 

0
1 
2

Explanation

Test case 1$1$: The GCD of all integers in the array is already 1$1$, which is odd.

Test case 2$2$: You choose the index i=2$i=2$ and set A2=⌊62 ⌋=⌊3⌋=3$A_2=\lfloor \frac{6}{2}\rfloor =\lfloor 3\rfloor =3$. So the array becomes [4,3]$[4,3]$ and the GCD of 4$4$ and 3$3$ is 

Solution on python 

def find(n):
    cnt = 0
    while n > 0 and n % 2 != 1:
        cnt += 1
        n //= 2
        
    return cnt
    
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    e = 0
    o = 0
    m = 1000000000
    for i in l:
        if i % 2 == 1: o += 1
        else:
            m = min(m, find(i))
            e += 1
    
    if o == 0: print(m)
    else: print(0)

def find(n):

cnt = 0

while n > 0 and n % 2 != 1:

cnt += 1

n //= 2

return cnt

for _ in range(int(input())):

n = int(input())

l = list(map(int, input().split()))

e = 0

o = 0

m = 1000000000

for i in l:

if i % 2 == 1: o += 1

else:

m = min(m, find(i))

e += 1

if o == 0: print(m)

else: print(0)

 

 

def find(n):
    cnt = 0
    while n > 0 and n % 2 != 1:
        cnt += 1
        n //= 2
        
    return cnt
    
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    e = 0
    o = 0
    m = 1000000000
    for i in l:
        if i % 2 == 1: o += 1
        else:
            m = min(m, find(i))
            e += 1
    
    if o == 0: print(m)
    else: print(0)