Amazon Online Assessment Problem[Ended on 21st March]

Revision en1, by AjaySabarish, 2021-03-22 17:09:03

You are given an array of N integers (N is even), at each round you have to select 2 numbers $$$(A[i],A[j])$$$, and do $$$ Sum = Sum + GCD(A[i], A[j]) * round $$$, post calculating sum remove those 2 numbers from Array. What is the maximum possible sum you can obtain?

Round's value starts from 1.

Constraints

$$$ 2 \leq N \leq 20 $$$

$$$ 1 \leq A[i] \leq 1e9 $$$

I tried Bitmasking Dp ( $$$ O(2 ^N * N ^2) $$$ ) but got TLE.

Example :

2 3 5 9

1st Round — 2 5, Sum = GCD(2,5) * 1

2nd Round — 3 9, Sum = GCD(3,9) * 2

The maximum possible sum is 7

Any insights?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English AjaySabarish 2021-03-22 17:09:03 651 Initial revision (published)