Dado un entero positivo N , la tarea es construir la secuencia ordenada más larga de elementos únicos cuyo MCM de sea igual a N .
Ejemplos:
Entrada: N = 12
Salida: 1 2 3 4 6 12
Explicación:
MCM de {1, 2, 3, 4, 6, 12 } es N( = 12).
Por lo tanto, la sucesión más larga posible es {1, 2, 3, 4, 6, 12}.Entrada: N = 9
Salida: 1 3 9
Explicación:
MCM de { 1, 2, 9 } es N( = 9).
Por lo tanto, la sucesión más larga posible es {1, 3, 9}.
Planteamiento: El problema se puede resolver con base en la siguiente observación:
Si un elemento de la array no es un factor de N, entonces el MCM de los elementos de la array nunca será N. Por lo tanto, los elementos de la array deben ser el factor de N.
Siga los pasos a continuación para resolver este problema:
- Inicialice una array , digamos newArr[] , para almacenar todos los elementos únicos de la array cuyo LCM sea igual a N.
- Encuentre todos los factores de N y almacénelos en newArr[] .
- Ordene la array newArr[] .
- Imprime todos los elementos de la array de newArr[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to construct an array of
// unique elements whose LCM is N
void constructArrayWithGivenLCM(int N)
{
// Stores array elements
// whose LCM is N
vector<int> newArr;
// Iterate over the range
// [1, sqrt(N)]
for (int i = 1; i * i <= N;
i++) {
// If N is divisible
// by i
if (N % i == 0) {
// Insert i into newArr[]
newArr.push_back(i);
// If N is not perfect square
if (N / i != i) {
newArr.push_back(N / i);
}
}
}
// Sort the array newArr[]
sort(newArr.begin(), newArr.end());
// Print array elements
for (auto i : newArr) {
cout << i << " ";
}
}
// Driver Code
int main()
{
// Given N
int N = 12;
// Function Call
constructArrayWithGivenLCM(N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.Arrays;
class GFG{
// Function to construct an array of
// unique elements whose LCM is N
static void constructArrayWithGivenLCM(int N)
{
// Stores array elements
// whose LCM is N
int newArr[] = new int[N];
int j = 0;
// Iterate over the range
// [1, sqrt(N)]
for(int i = 1; i * i <= N; i++)
{
// If N is divisible
// by i
if (N % i == 0)
{
// Insert i into newArr[]
newArr[j] = i;
j++;
// If N is not perfect square
if (N / i != i)
{
newArr[j] = N / i;
j++;
}
}
}
// Sort the array newArr[]
Arrays.sort(newArr);
// Print array elements
for(int i = j; i < N; i++)
{
System.out.print(newArr[i] + " ");
}
}
// Driver Code
public static void main (String[] args)
{
// Given N
int N = 12;
// Function Call
constructArrayWithGivenLCM(N);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program to implement # the above approach from math import sqrt,ceil,floor # Function to construct an array of # unique elements whose LCM is N def constructArrayWithGivenLCM(N): # Stores array elements # whose LCM is N newArr = [] # Iterate over the range # [1, sqrt(N)] for i in range(1, ceil(sqrt(N + 1))): # If N is divisible # by i if (N % i == 0): # Insert i into newArr[] newArr.append(i) # If N is not perfect square if (N // i != i): newArr.append(N // i) # Sort the array newArr[] newArr = sorted(newArr) # Print array elements for i in newArr: print(i, end = " ") # Driver Code if __name__ == '__main__': # Given N N = 12 # Function Call constructArrayWithGivenLCM(N) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to construct an array of
// unique elements whose LCM is N
static void constructArrayWithGivenLCM(int N)
{
// Stores array elements
// whose LCM is N
int []newArr = new int[N];
int j = 0;
// Iterate over the range
// [1, sqrt(N)]
for(int i = 1; i * i <= N; i++)
{
// If N is divisible
// by i
if (N % i == 0)
{
// Insert i into newArr[]
newArr[j] = i;
j++;
// If N is not perfect square
if (N / i != i)
{
newArr[j] = N / i;
j++;
}
}
}
// Sort the array newArr[]
Array.Sort(newArr);
// Print array elements
for(int i = j; i < N; i++)
{
Console.Write(newArr[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given N
int N = 12;
// Function Call
constructArrayWithGivenLCM(N);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to implement the above approach
// Function to construct an array of
// unique elements whose LCM is N
function constructArrayWithGivenLCM(N)
{
// Stores array elements
// whose LCM is N
let newArr = new Array(N);
newArr.fill(0);
let j = 0;
// Iterate over the range
// [1, sqrt(N)]
for(let i = 1; i * i <= N; i++)
{
// If N is divisible
// by i
if (N % i == 0)
{
// Insert i into newArr[]
newArr[j] = i;
j++;
// If N is not perfect square
if (parseInt(N / i, 10) != i)
{
newArr[j] = parseInt(N / i, 10);
j++;
}
}
}
// Sort the array newArr[]
newArr.sort(function(a, b){return a - b});
// Print array elements
for(let i = j; i < N; i++)
{
document.write(newArr[i] + " ");
}
}
// Given N
let N = 12;
// Function Call
constructArrayWithGivenLCM(N);
</script>
Producción:
1 2 3 4 6 12
Complejidad temporal: O(√ N)
Espacio auxiliar: O(1)