Dada una array a[] de n elementos. La tarea es encontrar la array (digamos b[]) de n + 1 tal que el Máximo Común Divisor de b[i] y b[i + 1] sea igual a a[i]. Si existe una solución múltiple, imprima aquella cuya suma de array sea mínima.
Ejemplos:
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
Supongamos que solo hay un número en la array dada a[]. Sea K, entonces ambos números en la array construida (digamos b[]) serán K y K.
Entonces, el valor de b[0] será solo a[0]. Ahora considere que hemos terminado hasta el índice i , es decir, ya hemos procesado hasta el índice i y hemos calculado b[i + 1].
Ahora el mcd(b[i + 1], b[i + 2]) = a[i + 1] y mcd(b[i + 2], b[i + 3]) = a[i + 2]. Entonces, b[i + 2] >= mcm(a[i + 1], a[i + 2]). O bien, b[i + 2] será múltiplo de mcm(a[i + 1], a[i + 2]). Como queremos la suma mínima, queremos el valor mínimo de b[i + 2]. Entonces, b[i + 2] = mcm(a[i + 2], a[i + 3]).
A continuación se muestra la implementación de este enfoque:
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 array
void 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 Program
int 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 array
import 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 b def __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 array def 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 code a = [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 array
using 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 b
function __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 array
function 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 array
function __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 array
function 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 Program
var a = [ 1, 2, 3 ];
var n = a.length;
printArray(a, n);
// This code is contributed by rrrtnx.
</script>
Producción
1 2 6 3