Divisibility by 2^n (Codeforces 1744D)
Tags: Greedy, sortings

You are given an array of positive integers $$$a_1, a_2, \ldots, a_n$$$.Make the product of all the numbers in the array (that is, $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n$$$) divisible by $$$2^n$$$.You can perform the following operation as many times as you like:  select an arbitrary index $$$i$$$ ($$$1 \leq i \leq n$$$) and replace the value $$$a_i$$$ with $$$a_i=a_i \cdot i$$$. You cannot apply the operation repeatedly to a single index. In other words, all selected values of $$$i$$$ must be different.Find the smallest number of operations you need to perform to make the product of all the elements in the array divisible by $$$2^n$$$. Note that such a set of operations does not always exist.

Input: The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4$$$) — the number test cases.Then the descriptions of the input data sets follow.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of array $$$a$$$.The second line of each test case contains exactly $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ values over all test cases in a test does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print the least number of operations to make the product of all numbers in the array divisible by $$$2^n$$$. If the answer does not exist, print -1.

Note: In the first test case, the product of all elements is initially $$$2$$$, so no operations needed.In the second test case, the product of elements initially equals $$$6$$$. We can apply the operation for $$$i = 2$$$, and then $$$a_2$$$ becomes $$$2\cdot2=4$$$, and the product of numbers becomes $$$3\cdot4=12$$$, and this product of numbers is divided by $$$2^n=2^2=4$$$. In the fourth test case, even if we apply all possible operations, we still cannot make the product of numbers divisible by $$$2^n$$$  — it will be $$$(13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304$$$, which does not divide by $$$2^n=2^4=16$$$.In the fifth test case, we can apply operations for $$$i = 2$$$ and $$$i = 4$$$. 

Sample Inputs:
6
1
2
2
3 2
3
10 6 11
4
13 17 1 1
5
1 1 12 1 1
6
20 7 14 18 3 5

Sample Outputs:
0
1
1
-1
2
1

Solution (Python):
def order(num):
    order = 0
    while not num % 2:
        num //= 2
        order += 1
    return order

def solve():
    n = int(input())
    temp = n
    nums = list(map(int, input().split()))
    for i in nums:
        while not i % 2:
            i //= 2
            n -= 1
        if n <= 0:
            print(0)
            return
    count = 0
    order(10)
    nums = list((order(i) for i in range(2, temp + 1, 2)))
    nums.sort()
    for i in range(len(nums) - 1, -1, -1):
        count += 1
        n -= nums[i]
        if n <= 0:
            print(count)
            return
    print(-1)
    return
for _ in range(int(input())):
    solve()

Solution (Python):
import math
n = int(input())
ris = [0 for i in range(n)]
for i in range(n):
    m = int(input())
    num = list(map(int, input().split()))
    pow = 0
    for j in range(m):
        while num[j] % 2 == 0 and pow < m:
            num[j] = num[j] / 2
            pow += 1
    r = m - pow
    binm = str(bin(m))[2:]
    a = [0 for j in range(len(binm) - 1)]
    for j in range(len(binm) - 1):
        if binm[j] == '1':
            a[j] += 1
            t = 1
            for k in range(j + 1, len(binm) - 1):
                a[k] += t
                t *= 2
    t = len(a)
    j = 0
    while j < len(a):
        while a[j] > 0:
            if r > 0:
                ris[i] += 1
                r -= t
                a[j] -= 1
            else:
                a[j] = 0
                j = len(a) - 1
        j += 1
        t -= 1
    if r > 0:
        ris[i] = -1
print(*ris, sep='\n')

Solution (Python):
def count_2(ai):
    res = 0
    while not ai % 2:
        ai = ai // 2
        res += 1
    return res

def output(a, n):
    n2 = 0
    res = 0
    for ai in a:
        n2 += count_2(ai)
        if n2 > n:
            return 0
    nearest_2 = 1
    n1 = n
    while n1 >= 2 ** nearest_2:
        nearest_2 += 1
    nearest_2 -= 1
    n_2 = 1
    t_selected = 0
    while n2 < n and nearest_2 > 0:
        if n_2 > 0:
            n2 += nearest_2
            n_2 -= 1
            res += 1
            t_selected += 1
        else:
            nearest_2 -= 1
            n_2 = n // 2 ** nearest_2 - t_selected
    if n2 < n:
        return -1
    return res
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    res = output(a, n)
    print(res)