HackerRank Number Theory – John and GCD list

Challenge: John and GCD list

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734630

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/john-and-gcd-list/problem

Cerinta

John is new to Mathematics and does not know how to calculate [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) of numbers. So he wants you to help him in 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 the list _B_ in which sum of all elements is minimum. It is guaranteed that such a list will always exist.
 
**Input Format**  
The first line contains an integer _T_, i.e., the number of the test cases. _T_ testcases follow.    
The first line of each test case contains an integer _N_, i.e., the number of elements in the array.  
The second line of each test case contains _N_ space separated integers that  denote the elements of the list _A_.  

**Output Format**  
For each test case, print in a new line the list _B_ such that each element is separated by a single space. 

**Constraints**  
1 ≤ _T_ ≤ 10   
2 ≤ _N_ ≤ 10<sup>3</sup>  
1 ≤ _A[i]_ ≤ 10<sup>4</sup>  
1 ≤ _B[i]_  

**Sample Input**  

    2
    3
    1 2 3
    3
    5 10 5
    
**Sample Output**  

    1 2 6 3
    5 10 10 5

**Explanation**  

For the first testcase, 

     GCD(1,2) = 1
     GCD(2,6) = 2
     GCD(6,3) = 3
     sum = 1+2+6+3 = 12 which is minimum among all possible list B

For the second testcase, 

    GCD(5, 10) = 5
    GCD(10, 10) = 10
    GCD(10, 5) = 5
    sum = 5 + 10 + 10 + 5 = 30 which is the minimum among all possible list B

Cod sursa

//john-and-gcd-list.cpp
//John and GCD list
//Weekly Challenges - Week 8
//Author: derekhh

#include<iostream>
using namespace std;

int a[1000];

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> a[i];
		cout << a[0] << " ";
		for (int i = 1; i < n; i++)
			cout << lcm(a[i - 1], a[i]) << " ";
		cout << a[n - 1] << endl;
	}
	return 0;
}