Given an array a[] of n elements. The task is to find the array (say b[]) of n + 1 such that Greatest Common Divisor of b[i] and b[i + 1] is equals to a[i]. If multiple solutions exist, print the one whose array sum is minimum.
Examples:
Input : a[] = { 1, 2, 3 }
Output : 1 2 6 3
GCD(1, 2) = 1
GCD(2, 6) = 2
GCD(6, 3) = 3
Also, 1 + 2 + 6 + 3 = 12 which is smallest among all
possible value of array that can be constructed.
Input : a[] = { 5, 10, 5 }
Output : 5 10 10 5
Suppose there is only one number in the given array a[]. Let it be K, and then both numbers in the constructed array (say b[]) will be K and K.
So, the value of the b[0] will be a[0] only. Now consider that, we are done up to index i i.e we have already processed upto index i and calculated b[i + 1].
Now the gcd(b[i + 1], b[i + 2]) = a[i + 1] and gcd(b[i + 2], b[i + 3]) = a[i + 2]. So, b[i + 2] >= lcm(a[i + 1], a[i + 2]). Or, b[i + 2] will be multiple of lcm(a[i + 1], a[i + 2]). As we want the minimum sum, so we want the minimum value of b[i + 2]. So, b[i + 2] = lcm(a[i + 2], a[i + 3]).
Below is the implementation of this approach:
C++
// CPP Program to construct an array whose GCD of// every consecutive element is the given array#include <bits/stdc++.h>using namespace std;// Return the LCM of two numbers.int lcm(int a, int b){ return (a * b) / __gcd(a, b);}// Print the required constructed arrayvoid printArray(int a[], int n){ // printing the first element. cout << a[0] << " "; // finding and printing the LCM of consecutive // element of given array. for (int i = 0; i < n - 1; i++) cout << lcm(a[i], a[i + 1]) << " "; // printing the last element of the given array. cout << a[n - 1] << endl;}// Driven Programint main(){ int a[] = { 1, 2, 3 }; int n = sizeof(a) / sizeof(a[0]); printArray(a, n); return 0;} |
Java
// Java Program to construct an array whose// GCD of every consecutive element is the// given arrayimport java.io.*;class GFG { // Recursive function to return gcd of // a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Return the LCM of two numbers. static int lcm(int a, int b) { return (a * b) / __gcd(a, b); } // Print the required constructed array static void printArray(int a[], int n) { // printing the first element. System.out.print( a[0] + " "); // finding and printing the LCM of // consecutive element of given array. for (int i = 0; i < n - 1; i++) System.out.print(lcm(a[i], a[i + 1]) + " "); // printing the last element of the // given array. System.out.print(a[n - 1]); } // Driven Program public static void main (String[] args) { int a[] = { 1, 2, 3 }; int n = a.length; printArray(a, n); }}// This code is contributed by anuj_67. |
Python3
# Python Program to construct an array whose# GCD of every consecutive element is the# given array# Recursive function to return gcd of# a and bdef __gcd( a, b): # Everything divides 0 if (a == 0 or b == 0): return 0 # base case if (a == b): return a # a is greater if (a > b): return __gcd(a - b, b) return __gcd(a, b - a) # Return the LCM of two numbers.def lcm(a, b): return (a * b) / __gcd(a, b)# Print the required constructed arraydef printArray(a, n): # printing the first element. print ( str(a[0]) + " ") # finding and printing the LCM of # consecutive element of given array. for i in range(0,n-1): print (str(lcm(a[i],a[i + 1])) + " ") # printing the last element of the # given array. print (a[n - 1])# Driver codea = [1, 2, 3 ]n = len(a)printArray(a, n)# This code is contributed by Prateek Bajaj |
C#
// C# Program to construct an array whose// GCD of every consecutive element is the// given arrayusing System;class GFG { // Recursive function to return // gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Return the LCM of two numbers. static int lcm(int a, int b) { return (a * b) / __gcd(a, b); } // Print the required constructed array static void printArray(int []a, int n) { // printing the first element. Console.Write( a[0] + " "); // finding and printing the LCM of // consecutive element of given array. for (int i = 0; i < n - 1; i++) Console.Write(lcm(a[i], a[i + 1]) + " "); // printing the last element // of the given array. Console.Write(a[n - 1]); } // Driver Code public static void Main () { int []a = {1, 2, 3}; int n = a.Length; printArray(a, n); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP Program to construct // an array whose GCD of// every consecutive element// is the given array// Recursive function to // return gcd of a and bfunction __gcd($a, $b){ // Everything divides 0 if($a == 0 or $b == 0) return 0 ; // base case if($a == $b) return $a ; // a is greater if($a > $b) return __gcd( $a - $b , $b ) ; return __gcd( $a , $b - $a ) ;}// Return the LCM of two numbers.function lcm($a, $b){ return ($a * $b) / __gcd($a, $b);}// Print the required constructed arrayfunction printArray( $a, $n){ // printing the first element. echo $a[0] , " "; // finding and printing // the LCM of consecutive // element of given array. for ( $i = 0; $i < $n - 1; $i++) echo lcm($a[$i], $a[$i + 1]) , " "; // printing the last element // of the given array. echo $a[$n - 1] ,"\n";} // Driver Code $a = array(1, 2, 3); $n = count($a); printArray($a, $n);// This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript Program to construct an array whose GCD of// every consecutive element is the given arrayfunction __gcd(a, b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); }// Return the LCM of two numbers.function lcm(a, b){ return (a * b) / __gcd(a, b);}// Print the required constructed arrayfunction printArray(a, n){ // printing the first element. document.write( a[0] + " "); // finding and printing the LCM of consecutive // element of given array. for (var i = 0; i < n - 1; i++) document.write( lcm(a[i], a[i + 1]) + " "); // printing the last element of the given array. document.write( a[n - 1] + "<br>");}// Driven Programvar a = [ 1, 2, 3 ];var n = a.length;printArray(a, n);// This code is contributed by rrrtnx.</script> |
Output
1 2 6 3
Complexity Analysis:
- Time complexity: O(n * log(max(a, b)), where n represents the size of the given array.
- Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
