Dada una secuencia Y de tamaño N donde:
Y i = mcd(X 1 , X 2 , X 3 , . . ., X i ) de alguna sucesión X.
La tarea es encontrar tal secuencia X si tal X es posible.
Nota: Si X existe, puede haber múltiples valores posibles para X. Generar cualquiera es suficiente.
Ejemplos:
Entrada: N = 2, Y = [4, 2]
Salida: [4, 2]
Explicación: Y 0 = mcd(X 0 ) = X 0 = 4. Y mcd(4, 2) = 2 = Y 1 .Entrada: [1, 3]
Salida: -1
Explicación: No se puede formar tal secuencia.
Planteamiento: El problema se puede resolver con base en la siguiente observación:
- i-ésimo elemento de Y = mcd(X 1 , X 2 , X 3 , . . ., X i ) y (i+1)ésimo elemento de Y = mcd(X 1 , X 2 , X 3 , . . ., X i, X i+1 ).
- Entonces (i+1) el elemento de Y puede escribirse como mcd(mcd(X 1 , X 2 , X 3 , . . ., X i ), X i+1 ) ——-(1) es decir, mcd( a, b, c) = mcd( mcd(a, b), c ).
- Entonces (i+1) el elemento de Y es mcd (el elemento de Y, X (i+1)) de la ecuación 1.
- Por lo tanto , el (i+1)-ésimo elemento de Y debe ser factor del i-ésimo elemento de Y, ya que el mcd de dos elementos es divisor de ambos elementos.
- Dado que (i+1) el elemento de Y divide el elemento i de Y, mcd (el elemento i, (i+1) el elemento) siempre es igual al (i+1) el elemento.
Siga la ilustración a continuación:
Ilustración:
Por ejemplo: N = 2, Y = {4, 2}
- X[0] = Y[0] = 4 porque cualquier número es MCD de sí mismo.
- Y[1] = MCD(X[0], X[1]). Ahora MCD(X[0]) = Y[0]. Entonces Y[1] = MCD(Y[0], X[1]). Por lo tanto, Y[1] debería ser un factor de Y[0].
- En el ejemplo dado, 2 es un factor de 4. Por lo tanto, es posible formar una secuencia X y X[1] puede ser igual que Y[1].
Asignar X[1] = 2 satisface MCD (X[0, X[1]) = Y[1] = 2.- Así que la secuencia final X es {4, 2}.
Así que siga los pasos que se mencionan a continuación para resolver el problema basado en la observación anterior:
- Comience a atravesar Y desde el inicio de la secuencia.
- Si en la Secuencia dada Y tiene algún (i+1)-ésimo elemento que no se divide en -ésimo elemento, entonces la secuencia X no se puede generar .
- Si el (i+1)-ésimo elemento divide al i-ésimo elemento, entonces existe una secuencia X y se puede encontrar por la conclusión anterior de que el (i+1)-ésimo elemento de Y
es mcd(-ésimo elemento de Y, X i+1 ) y X i+1 = Y i+1 es un valor posible para X i+1 .
A continuación se muestra la implementación del enfoque:
C++
// C++ Program to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Euclidean theorem to find gcd
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is possible
// to generate lost sequence X
void checkforX(int Y[], int N)
{
int cur_gcd = Y[0];
bool Xexist = true;
// Loop to check existence of X
for (int i = 1; i < N; i++) {
cur_gcd = gcd(cur_gcd, Y[i]);
if (cur_gcd != Y[i]) {
Xexist = false;
break;
}
}
// Sequence X is found
if (Xexist) {
// Loop to generate X
for (int i = 0; i < N; i++)
cout << Y[i] << ' ';
}
// Sequence X can't be generated
else {
cout << -1 << endl;
}
}
// Driver code
int main()
{
int N = 2;
// Sequence Y of size 2
int Y[] = { 4, 2 };
checkforX(Y, N);
return 0;
}
C
// C program to implement above approach
#include <stdio.h>
// Euclidean theorem to calculate gcd
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is possible
// to generate lost sequence X
void checkforX(int Y[], int N)
{
int cur_gcd = Y[0];
int Xexist = 1;
// Loop to check existence of X
for (int i = 1; i < N; i++) {
cur_gcd = gcd(cur_gcd, Y[i]);
if (cur_gcd != Y[i]) {
Xexist = 0;
break;
}
}
// Sequence X is found
if (Xexist) {
// Loop to generate X
for (int i = 0; i < N; i++)
printf("%d ", Y[i]);
}
// Sequence X can't be generated
else {
printf("-1");
}
}
// Driver code
int main()
{
int N = 2;
// Sequence Y of size 2
int Y[] = { 4, 2 };
checkforX(Y, N);
return 0;
}
Java
// Java Program to implement above approach
import java.util.*;
class GFG{
// Euclidean theorem to find gcd
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is possible
// to generate lost sequence X
static void checkforX(int Y[], int N)
{
int cur_gcd = Y[0];
boolean Xexist = true;
// Loop to check existence of X
for (int i = 1; i < N; i++) {
cur_gcd = gcd(cur_gcd, Y[i]);
if (cur_gcd != Y[i]) {
Xexist = false;
break;
}
}
// Sequence X is found
if (Xexist) {
// Loop to generate X
for (int i = 0; i < N; i++)
System.out.print(Y[i] +" ");
}
// Sequence X can't be generated
else {
System.out.print(-1 +"\n");
}
}
// Driver code
public static void main(String[] args)
{
int N = 2;
// Sequence Y of size 2
int Y[] = { 4, 2 };
checkforX(Y, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python code for the above approach # Euclidean theorem to find gcd def gcd(a, b): if (b == 0): return a return gcd(b, a % b) # Function to check if it is possible # to generate lost sequence X def checkforX(Y, N): cur_gcd = Y[0] Xexist = True # Loop to check existence of X for i in range(1, N): cur_gcd = gcd(cur_gcd, Y[i]) if (cur_gcd != Y[i]): Xexist = False break # Sequence X is found if (Xexist): # Loop to generate X for i in range(N): print(Y[i], end=' ') # Sequence X can't be generated else: print(-1) # Driver code N = 2 # Sequence Y of size 2 Y = [4, 2] checkforX(Y, N) # This code is contributed by gfgking
C#
// C# Program to implement above approach
using System;
class GFG
{
// Euclidean theorem to find gcd
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is possible
// to generate lost sequence X
static void checkforX(int []Y, int N)
{
int cur_gcd = Y[0];
bool Xexist = true;
// Loop to check existence of X
for (int i = 1; i < N; i++) {
cur_gcd = gcd(cur_gcd, Y[i]);
if (cur_gcd != Y[i]) {
Xexist = false;
break;
}
}
// Sequence X is found
if (Xexist) {
// Loop to generate X
for (int i = 0; i < N; i++)
Console.Write(Y[i] + " ");
}
// Sequence X can't be generated
else {
Console.Write(-1);
}
}
// Driver code
public static void Main()
{
int N = 2;
// Sequence Y of size 2
int []Y = { 4, 2 };
checkforX(Y, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Euclidean theorem to find gcd
function gcd(a, b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is possible
// to generate lost sequence X
function checkforX(Y, N) {
let cur_gcd = Y[0];
let Xexist = true;
// Loop to check existence of X
for (let i = 1; i < N; i++) {
cur_gcd = gcd(cur_gcd, Y[i]);
if (cur_gcd != Y[i]) {
Xexist = false;
break;
}
}
// Sequence X is found
if (Xexist) {
// Loop to generate X
for (let i = 0; i < N; i++)
document.write(Y[i] + ' ');
}
// Sequence X can't be generated
else {
document.write(-1 + '<br>');
}
}
// Driver code
let N = 2;
// Sequence Y of size 2
let Y = [4, 2];
checkforX(Y, N);
// This code is contributed by Potta Lokesh
</script>
Producción
4 2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)