Dado un número entero N , la tarea es construir la array A[] más larga posible, de modo que se cumplan las siguientes condiciones:
- A[0] = N.
- No deben ser iguales dos elementos adyacentes.
- Para todo i (0 < i < longitud del arreglo), tal que A[i] es divisible por A[i + 1]
Nota: si hay muchas secuencias posibles, imprima cualquier secuencia.
Ejemplos:
Entrada: N = 10
Salida: 3, {10, 2, 1}
Explicación: L a longitud máxima posible de la array A[] es 3
, que es {10, 2, 1}. Por lo tanto, no es posible una array más grande para N = 10Entrada: N = 8
Salida: 4, {8, 4, 2, 1}
Enfoque: La intuición para resolver este problema y maximizar la longitud de la secuencia es:
Para cada elemento, simplemente busque el divisor más alto (aparte del número en sí) del número anterior que, a cambio, tendrá el máximo número de divisores posible.
Siga la ilustración a continuación para una mejor comprensión.
Ilustración:
Considere N = 8;
- N = 8, divisor más alto = 4
- Entonces, en el siguiente paso N = 4
- N = 4, divisor más alto = 2
- Entonces, en el siguiente paso N = 2
- N = 2, divisor más alto = 1
- Aquí, la condición base se alcanza, por lo tanto, deténgase.
Los siguientes son los pasos para implementar el enfoque anterior:
- Ejecutar un bucle hasta que N sea mayor que 1
- Encuentra todos los divisores del número .
- Asignar el máximo divisor del número a N
- En el último empuje 1 a la array resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ function to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sequence
vector<int> getMaximumSequence(int& N)
{
// vector to store the sequence
vector<int> sequence;
// Base case
if (N == 1) {
sequence.push_back(1);
return sequence;
}
else {
// Run the loop till the N is
// greater than 1
while (N > 1) {
// Push the number in the
// sequence
sequence.push_back(N);
// Declare maximum as 1 because
// 1 is always the divisor
// of the Number
int maxx = 1;
// Vector to track the
// maximum divisors
vector<int> ds;
ds.push_back(1);
// Run a loop to find out all
// the divisors except 1 and N
for (int i = 2; i <= sqrt(N);
i++) {
// If i is divisor of the
// number then push_back it
// in the ds vector
if (N % i == 0) {
ds.push_back(i);
ds.push_back(N / i);
}
}
// Assign N the maximum
// divisors to get the
// maximum sequence possible
N = *max_element(ds.begin(),
ds.end());
}
// N will be equal to 1 thus,
// push back it in the sequence
// vector to complete the sequence
sequence.push_back(N);
return sequence;
}
}
// Function to print sequence
void printSequence(vector<int>& res)
{
cout << res.size() << "\n";
for (auto x : res) {
cout << x << " ";
}
}
// Driver Function
int main()
{
int N = 8;
// Function call
vector<int> res = getMaximumSequence(N);
printSequence(res);
return 0;
}
Java
// JAVA function to implement above approach
import java.util.*;
class GFG {
// Function to find the maximum sequence
public static ArrayList<Integer>
getMaximumSequence(int N)
{
// vector to store the sequence
ArrayList<Integer> sequence
= new ArrayList<Integer>();
// Base case
if (N == 1) {
sequence.add(1);
return sequence;
}
else {
// Run the loop till the N is
// greater than 1
while (N > 1) {
// Push the number in the
// sequence
sequence.add(N);
// Declare maximum as 1 because
// 1 is always the divisor
// of the Number
int maxx = 1;
// Vector to track the
// maximum divisors
ArrayList<Integer> ds
= new ArrayList<Integer>();
ds.add(1);
// Run a loop to find out all
// the divisors except 1 and N
for (int i = 2; i <= Math.sqrt(N); i++) {
// If i is divisor of the
// number then push_back it
// in the ds vector
if (N % i == 0) {
ds.add(i);
ds.add(N / i);
}
}
// Assign N the maximum
// divisors to get the
// maximum sequence possible
N = Collections.max(ds);
}
// N will be equal to 1 thus,
// push back it in the sequence
// vector to complete the sequence
sequence.add(N);
return sequence;
}
}
// Function to print sequence
public static void printSequence(ArrayList<Integer> res)
{
System.out.println(res.size());
for (int x : res) {
System.out.print(x + " ");
}
}
// Driver Function
public static void main(String[] args)
{
int N = 8;
// Function call
ArrayList<Integer> res = getMaximumSequence(N);
printSequence(res);
}
}
// This code is contributed by Taranpreet
Python3
# Python3 program to implement the above approach
# Function to find the maximum sequence
def getMaximumSequence(N):
# vector to store the sequence
sequence = []
# Base case
if N == 1:
sequence.append(1)
return sequence
else:
# Run the loop till the N is
# greater than 1
while N > 1:
# push the number in the
# sequence
sequence.append(N)
# Declare maximum as 1 because
# 1 is always the divisor
# of the Number
maxx = 1
# Vector to track the
# maximum divisors
ds = []
ds.append(1)
# Run a loop to find out all
# the divisors
for i in range(2, 1 + int(N ** 0.5)):
# If i is divisor of the
# number then push_back it
# in the ds vector
if N % i == 0:
ds.append(i)
ds.append(N // i)
# Assign N the maximum
# divisors to get the
# maximum sequence possible
N = max(ds)
# N will be equal to 1 thus,
# push back it in the sequence
# vector to complete the sequence
sequence.append(N)
return sequence
# function to print the sequence
def printSequence(res):
print(len(res))
print(" ".join(list(map(str, res))))
# Driver Code
N = 8
# Function Call
res = getMaximumSequence(N)
printSequence(res)
# This code is contributed by phasing17
C#
// C# function to implement above approach
using System;
using System.Collections.Generic;
using System.Linq;
public class GFG
{
// Function to find the maximum sequence
public static List<int> getMaximumSequence(int N)
{
// list to store the sequence
List<int> sequence = new List<int>();
// Base case
if (N == 1) {
sequence.Add(1);
return sequence;
}
else {
// Run the loop till the N is
// greater than 1
while (N > 1) {
// Push the number in the
// sequence
sequence.Add(N);
// Vector to track the
// maximum divisors
List<int> ds = new List<int>();
ds.Add(1);
// Run a loop to find out all
// the divisors except 1 and N
for (int i = 2; i <= Math.Sqrt(N); i++) {
// If i is divisor of the
// number then push_back it
// in the ds vector
if (N % i == 0) {
ds.Add(i);
ds.Add(N / i);
}
}
// Assign N the maximum
// divisors to get the
// maximum sequence possible
N = ds.Max();
}
// N will be equal to 1 thus,
// push back it in the sequence
// vector to complete the sequence
sequence.Add(N);
return sequence;
}
}
// Function to print sequence
public static void printSequence(List<int> res)
{
Console.WriteLine(res.Count);
for (int x = 0; x < res.Count; x++) {
Console.Write(res[x] + " ");
}
}
public static void Main(string[] args)
{
int N = 8;
// Function call
List<int> res = getMaximumSequence(N);
printSequence(res);
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code for the above approach
// Function to find the maximum sequence
function getMaximumSequence(N) {
// vector to store the sequence
let sequence = [];
// Base case
if (N == 1) {
sequence.push(1);
return sequence;
}
else {
// Run the loop till the N is
// greater than 1
while (N > 1) {
// Push the number in the
// sequence
sequence.push(N);
// Declare maximum as 1 because
// 1 is always the divisor
// of the Number
let maxx = 1;
// Vector to track the
// maximum divisors
let ds = [];
ds.push(1);
// Run a loop to find out all
// the divisors except 1 and N
for (let i = 2; i <= Math.sqrt(N);
i++) {
// If i is divisor of the
// number then push_back it
// in the ds vector
if (N % i == 0) {
ds.push(i);
ds.push(Math.floor(N / i));
}
}
// Assign N the maximum
// divisors to get the
// maximum sequence possible
N = Math.max(...ds);
}
// N will be equal to 1 thus,
// push back it in the sequence
// vector to complete the sequence
sequence.push(N);
return sequence;
}
}
// Function to print sequence
function printSequence(res) {
document.write(res.length + '<br>');
for (let x of res) {
document.write(x + " ")
}
}
// Driver Function
let N = 8;
// Function call
let res = getMaximumSequence(N);
printSequence(res);
// This code is contributed by Potta Lokesh
</script>
Producción
4 8 4 2 1
Complejidad de tiempo: O(log 2 N * Sqrt(M))
Espacio auxiliar: O(log 2 N * M), donde M es el número de divisores y logN es el número de veces que se ejecuta el ciclo