John and GCD list

John is new to Mathematics and does not know how to calculate the GCD of numbers. So he wants you to help him with a few GCD calculations. John has a list A of numbers, indexed 1 to N. He wants to create another list B having N+1 numbers, indexed from 1 to N+1, and having the following property:

GCD(B[i], B[i+1]) = A[i], ∀ 1 ≤ i ≤ N

As there can be many such lists, John wants to know list B in which the sum of all elements is minimum. It is guaranteed that such a list will always exist.

Example:

Input:  n = 3, a = {1, 2, 3}
Output: 1 2 6 3

Approach

Java

import java.util.ArrayList;

public class GCDList {
    public static void main(String[] args) {

        int n = 3;
        int[] a = { 1, 2, 3 };
        ArrayList<Integer> result = solve(a);

        System.out.println(result);

    }

    static int GCD(int a, int b) {
        if (b == 0)
            return a;
        return GCD(b, a % b);
    }

    static ArrayList<Integer> solve(int[] a) {
        int n = a.length;
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(a[0]);
        for (int i = 1; i < n; ++i) {
            res.add(a[i - 1] * a[i] / GCD(a[i - 1], a[i]));
        }
        res.add(a[n - 1]);
        return res;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> solve(vector<int> a)
{
    int n = a.size();
    vector<int> res;
    res.push_back(a[0]);
    for (int i = 1; i < n; ++i)
    {
        res.push_back(a[i - 1] * a[i] / __gcd(a[i - 1], a[i]));
    }
    res.push_back(a[n - 1]);
    return res;
}

int main()
{

    int n = 3;
    vector<int> a = {1, 2, 3};
    vector<int> result = solve(a);

    for (int i = 0; i < n + 1; i++)
    {
        cout << result[i];

        if (i != n)
        {
            cout << " ";
        }
    }

    cout << "\n";

    return 0;
}