Prefix GCD Maximization

★★★★★

4.3

3 votes

Dynamic Programming, Dynamic Programming and Bit Masking, Introduction to Dynamic Programming 1, Algorithms, Bitmask, 1-D

Details

Submissions

Discussion

Editorial

Problem

You are given an array of size $N$ . Rearrange it in such a manner that the sum of the GCD over all the non-empty prefixes of the array is maximum.

GCD here means greatest common divisior. It is the largest number which divides any set of numbers without leaving any remainder with any of them.

Input format:

The first line contains a single integer $N$ .
The second line, contains $N$ space-separated integers, the array elements.

Output format:

Print the answer — the maximum possible sum of all the prefix GCD's of the rearranged array.

Constraints:

$1 \leq N \leq 20 \\ 1 \leq A_i \leq 10^9 \\$

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

Here we can rearrange the array as 12 6 8. This arrangemment the sum of the GCD of the prefix will be gcd(12)+gcd(12,6)+gcd(12,6,8). This would have the maximum possible sum of 20.