Dada una array de N elementos, encuentre el número mínimo de inserciones para convertir la array dada en una array coprima. Imprima también la array resultante.
Array coprimos: array en la que cada par de elementos adyacentes son coprimos. es decir, 
.
Ejemplos:
Input : A[] = {2, 7, 28}
Output : 1
Explanation :
Here, 1st pair = {2, 7} are co-primes( gcd(2, 7) = 1).
2nd pair = {7, 28} are not co-primes, insert 9
between them. gcd(7, 9) = 1 and gcd(9, 28) = 1.
Input : A[] = {5, 10, 20}
Output : 2
Explanation :
Here, there is no pair which are co-primes.
Insert 7 between (5, 10) and 1 between (10, 20).
Observe que para hacer que un par se convierta en coprimos, tenemos que insertar un número que haga que los pares recién formados sean coprimos. Entonces, tenemos que verificar cada par adyacente por su primalidad e insertar un número si es necesario. Ahora, ¿cuál es el número que se debe insertar? Tomemos dos números a y b. Si cualquiera de a o b es 1, entonces MCD(a, b) = 1. Entonces, podemos insertar UNO(1) en cada par. Por eficiencia usamos la función gcd de euler .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for minimum insertions to
// make a Co-prime Array.
#include <bits/stdc++.h>
using namespace std;
void printResult(int arr[], int n)
{
// Counting adjacent pairs that are not
// co-prime.
int count = 0;
for (int i = 1; i < n; i++)
if (__gcd(arr[i], arr[i - 1]) != 1)
count++;
cout << count << endl; // No.of insertions
cout << arr[0] << " ";
for (int i = 1; i < n; i++)
{
// If pair is not a co-prime insert 1.
if (__gcd(arr[i], arr[i - 1]) != 1)
cout << 1 << " ";
cout << arr[i] << " ";
}
}
// Driver Function
int main()
{
int A[] = { 5, 10, 20 };
int n = sizeof(A) / sizeof(A[0]);
printResult(A, n);
return 0;
}
Java
//Java program for minimum insertions
// to make a Co-prime 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);
}
static void printResult(int arr[], int n)
{
// Counting adjacent pairs that are not
// co-prime.
int count = 0;
for (int i = 1; i < n; i++)
if (gcd(arr[i], arr[i - 1]) != 1)
count++;
// No.of insertions
System.out.println(count );
System.out.print (arr[0] + " ");
for (int i = 1; i < n; i++)
{
// If pair is not a co-prime insert 1.
if (gcd(arr[i], arr[i - 1]) != 1)
System.out.print( 1 + " ");
System.out.print(arr[i] + " ");
}
}
// Driver Function
public static void main(String args[])
{
int A[] = { 5, 10, 20 };
int n = A.length;
printResult(A, n);
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python3 code for minimum insertions # to make a Co-prime Array. from fractions import gcd def printResult(arr, n): # Counting adjacent pairs that # are not co-prime. count = 0 for i in range(1,n): if (gcd(arr[i], arr[i - 1]) != 1): count+=1 print(count) # No.of insertions print( arr[0], end = " ") for i in range(1,n): # If pair is not a co-prime insert 1. if (gcd(arr[i], arr[i - 1]) != 1): print(1, end = " ") print(arr[i] , end = " ") # Driver Code A = [ 5, 10, 20 ] n = len(A) printResult(A, n) # This code is contributed by "Sharad_Bhardwaj".
C#
// C# program for minimum insertions
// to make a Co-prime 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);
}
static void printResult(int[] arr, int n)
{
// Counting adjacent pairs that
// are not co-prime.
int count = 0;
for (int i = 1; i < n; i++)
if (gcd(arr[i], arr[i - 1]) != 1)
count++;
// No.of insertions
Console.WriteLine(count);
Console.Write(arr[0] + " ");
for (int i = 1; i < n; i++) {
// If pair is not a co-prime insert 1.
if (gcd(arr[i], arr[i - 1]) != 1)
Console.Write(1 + " ");
Console.Write(arr[i] + " ");
}
}
// Driver Function
public static void Main()
{
int[] A = { 5, 10, 20 };
int n = A.Length;
printResult(A, n);
}
}
/*This code is contributed by vt_m.*/
PHP
<?php
// PHP program for minimum
// insertions to make a
// Co-prime Array.
// Recursive function to
// return gcd of a and b
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);
}
function printResult($arr, $n)
{
// Counting adjacent pairs
// that are not co-prime.
$count = 0;
for ($i = 1; $i < $n; $i++)
if (gcd($arr[$i],
$arr[$i - 1]) != 1)
$count++;
// No.of insertions
echo $count, "\n";
echo $arr[0] , " ";
for ($i = 1; $i < $n; $i++)
{
// If pair is not a
// co-prime insert 1.
if (gcd($arr[$i],
$arr[$i - 1]) != 1)
echo 1 , " ";
echo $arr[$i] , " ";
}
}
// Driver Code
$A = array(5, 10, 20);
$n = sizeof($A);
printResult($A, $n);
// This code is contributed
// by ajit
?>
Javascript
<script>
// Javascript program for minimum insertions
// to make a Co-prime Array.
// Recursive function to return
// gcd of a and b
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);
}
function printResult(arr, n)
{
// Counting adjacent pairs that
// are not co-prime.
let count = 0;
for(let i = 1; i < n; i++)
if (gcd(arr[i], arr[i - 1]) != 1)
count++;
// No.of insertions
document.write(count + "</br>");
document.write(arr[0] + " ");
for(let i = 1; i < n; i++)
{
// If pair is not a co-prime insert 1.
if (gcd(arr[i], arr[i - 1]) != 1)
document.write(1 + " ");
document.write(arr[i] + " ");
}
}
// Driver code
let A = [ 5, 10, 20 ];
let n = A.length;
printResult(A, n);
// This code is contributed by suresh07
</script>
Producción
2 5 1 10 1 20
Complejidad temporal: O(n).
Publicación traducida automáticamente
Artículo escrito por Harsha_Mogali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA