Arrays son una de las estructuras de datos más fundamentales en programación y muchos problemas requieren combinar, comparar o transformar sus elementos. En este artículo explicamos de forma clara el problema de reemplazar números adyacentes no coprimos por su MCM, los conceptos matemáticos involucrados, la estrategia eficiente y ejemplos de implementación en C++, JavaScript y Python. También incluimos un resumen de complejidad y cómo Q2BSTUDIO puede ayudar con soluciones a medida relacionadas con inteligencia artificial, ciberseguridad y servicios cloud.
Explicación del problema: dado un array nums de enteros, repetir el proceso de encontrar dos números adyacentes que no sean coprimos, reemplazarlos por su MCM y continuar hasta que no queden pares adyacentes no coprimos.
Conceptos matemáticos: MCD o GCD es el mayor divisor común de dos números. MCM o LCM es el menor múltiplo común. Dos números son no coprimos si su MCD es mayor que 1.
Ejemplo paso a paso con nums = [6, 4, 3, 2, 7, 6, 2]: Paso 1 comparar 6 y 4, MCD 2 mayor que 1, MCM 12, array pasa a [12, 3, 2, 7, 6, 2]. Paso 2 comparar 12 y 3, MCD 3, MCM 12, array pasa a [12, 2, 7, 6, 2]. Paso 3 comparar 12 y 2, MCD 2, MCM 12, array pasa a [12, 7, 6, 2]. Paso 4 comparar 6 y 2, MCD 2, MCM 6, array pasa a [12, 7, 6]. Ya no hay pares adyacentes no coprimos, resultado [12, 7, 6].
Estrategia y algoritmo: la forma más eficaz es usar una pila. Recorremos cada número del array y lo añadimos a la pila. Tras cada inserción comprobamos las dos últimas entradas de la pila; si su MCD es mayor que 1 calculamos su MCM, las eliminamos y empujamos el MCM. Repetimos mientras las dos últimas no sean coprimas. Al final la pila contiene el resultado final. Este enfoque evita combinaciones redundantes y aprovecha que cada fusión reduce el número de elementos.
Implementación en C++:
#include <iostream> #include <vector> #include <numeric> using namespace std ; class Solution { public: vector < int > replaceNonCoprimes ( vector < int >& nums ) { vector < int > st ; for ( int n : nums ) { st . push_back ( n ); int g ; while ( st . size () > 1 && ( g = gcd ( st . back (), st [ st . size () - 2 ] ) ) != 1 ) { long long a = st . back (); long long b = st [ st . size () - 2 ]; st . pop_back (); st . pop_back (); st . push_back (( a * b ) / g ); } } return st ; } }; int main () { Solution solution ; vector < int > nums = { 6 , 4 , 3 , 2 , 7 , 6 , 2 }; vector < int > result = solution . replaceNonCoprimes ( nums ); for ( int num : result ) cout << num << ' ' ; return 0 ; }
Implementación en JavaScript:
function gcd ( a , b ) { while ( b !== 0 ) { let temp = b ; b = a % b ; a = temp ; } return a ; } function replaceNonCoprimes ( nums ) { const stack = []; for ( let n of nums ) { stack . push ( n ); while ( stack . length > 1 ) { const last = stack [ stack . length - 1 ]; const secondLast = stack [ stack . length - 2 ]; const g = gcd ( last , secondLast ); if ( g === 1 ) break ; stack . pop (); stack . pop (); stack . push (( last * secondLast ) / g ); } } return stack ; } // Ejemplo const nums = [ 6 , 4 , 3 , 2 , 7 , 6 , 2 ]; console . log ( replaceNonCoprimes ( nums ));
Implementación en Python:
import math def replaceNonCoprimes ( nums ): stack = [] for n in nums : stack . append ( n ) while len ( stack ) > 1 : a = stack [ - 1 ] b = stack [ - 2 ] g = math . gcd ( a , b ) if g == 1 : break stack . pop () stack . pop () lcm = ( a * b ) // g stack . append ( lcm ) return stack # Ejemplo nums = [ 6 , 4 , 3 , 2 , 7 , 6 , 2 ] print ( replaceNonCoprimes ( nums ))
Complejidad: tiempo en el peor caso O(n log M) donde n es el número de elementos y M es el valor máximo en el array. Explicación sencilla: recorremos cada elemento una vez, cada fusión reduce el tamaño y las operaciones más costosas son los cálculos de MCD que toman tiempo logarítmico respecto al tamaño de los números. Espacio O(n) por la pila que almacena a lo sumo todos los elementos en el peor escenario.
Conclusiones y buenas prácticas: usar una pila es eficiente para gestionar fusiones locales. Conocer MCD y MCM permite razonar por qué el proceso es correcto y finaliza. El resultado final es único independientemente del orden de fusiones válido.
Sobre Q2BSTUDIO: somos una empresa de desarrollo de software especializada en aplicaciones a medida y software a medida, con experiencia en inteligencia artificial, ciberseguridad, servicios cloud aws y azure, inteligencia de negocio y soluciones de automatización. Si buscas desarrollar una aplicación robusta o integrar modelos de ia para empresas, podemos ayudarte con soluciones personalizadas. Conecta con nuestros servicios de desarrollo de aplicaciones a medida en desarrollo de aplicaciones y software a medida y descubre nuestras capacidades de inteligencia artificial en servicios de inteligencia artificial para empresas. También ofrecemos consultoría en ciberseguridad y pentesting, servicios cloud y proyectos de business intelligence con Power BI para transformar datos en decisiones.
Palabras clave: aplicaciones a medida, software a medida, inteligencia artificial, ciberseguridad, servicios cloud aws y azure, servicios inteligencia de negocio, ia para empresas, agentes IA, power bi.
Si necesitas que adaptemos este ejemplo a un caso real de negocio o que lo integremos en una aplicación con backend seguro y escalable, el equipo de Q2BSTUDIO está listo para colaborar.
.jpg)
