Divide and Multiply (Codeforces 1609A)
Tags: Greedy, number theory

  William has array of $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. He can perform the following sequence of operations any number of times:   Pick any two items from array $$$a_i$$$ and $$$a_j$$$, where $$$a_i$$$ must be a multiple of $$$2$$$  $$$a_i = \frac{a_i}{2}$$$  $$$a_j = a_j \cdot 2$$$ Help William find the maximal sum of array elements, which he can get by performing the sequence of operations described above.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). Description of the test cases follows.The first line of each test case contains an integer $$$n$$$ $$$(1 \le n \le 15)$$$, the number of elements in William's array.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i < 16)$$$, the contents of William's array.

Output: For each test case output the maximal sum of array elements after performing an optimal sequence of operations.

Note: In the first example test case the optimal sequence would be:   Pick $$$i = 2$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_2 = \frac{4}{2} = 2$$$ and $$$a_1 = 6 \cdot 2 = 12$$$, making the array look as: [12, 2, 2].  Pick $$$i = 2$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_2 = \frac{2}{2} = 1$$$ and $$$a_1 = 12 \cdot 2 = 24$$$, making the array look as: [24, 1, 2].  Pick $$$i = 3$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_3 = \frac{2}{2} = 1$$$ and $$$a_1 = 24 \cdot 2 = 48$$$, making the array look as: [48, 1, 1]. The final answer $$$48 + 1 + 1 = 50$$$.In the third example test case there is no way to change the sum of elements, so the answer is $$$10$$$.

Sample Inputs:
5
3
6 4 2
5
1 2 3 4 5
1
10
3
2 3 4
15
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

Sample Outputs:
50
46
10
26
35184372088846

Solution (Python):
for s in [*open(0)][2::2]:
    (*a,) = map(int, s.split())
    i = 0
    k = 1
    for x in a:
        x &= -x
        a[i] //= x
        k *= x
        i += 1
    print(sum(a) + max(a) * (k - 1))

Solution (Python):
from collections import *
from functools import *
import sys
input = lambda : sys.stdin.readline().rstrip()

@lru_cache(maxsize=None)
def d(x):
    b = 1
    while x % 2 == 0:
        x //= 2
        b *= 2
    return (x, b)
Z = int(input())
for _ in range(Z):
    n = int(input())
    (*arr,) = map(int, input().split())
    dp = [1] * n
    mutisum = 1
    for (i, j) in enumerate(arr):
        if j % 2 == 0:
            (arr[i], b) = d(j)
            mutisum *= b
    maxx = max(arr)
    print(mutisum * maxx + sum(arr) - maxx)

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    c = 0
    for i in range(n):
        while a[i] % 2 == 0:
            c += 1
            a[i] >>= 1
    print(max(a) * 2 ** c + (sum(a) - max(a)))