¿Cuál sería un enfoque / algoritmo eficiente para calcular el MCD por pares más alto a partir de una matriz de números dada?

Answer 1

No sé si es el mejor método, pero es eficiente, ya que funciona en O (n * logn). Recientemente resolví una pregunta en hackerrank.com basada en la pregunta que hiciste. Entonces mi enfoque es como:

Supongamos que MAX es el límite de cualquier elemento de la matriz, es decir, ai <= MAX. Ahora un número que dice x será el MCD de cualquier par en la matriz si ambos elementos del par son múltiplos de x. Entonces, podemos tener una verificación de todas las x desde MAX hasta 1 (en orden decreciente) si hay dos múltiplos presentes en la matriz o no. El número de múltiplos de x hasta MAX estaría alrededor de MAX / x y cada múltiplo se puede verificar por su presencia en la matriz en tiempo constante (marcando la matriz de entrada por adelantado). Entonces, la primera x para la cual se encuentran dos múltiplos en la matriz sería su respuesta.

La complejidad del tiempo sería O (MAX * log (X)) aproximadamente … como MAX / 1 + MAX / 2 + …… .. MAX / MAX es aproximadamente log (MAX) (la complejidad del tiempo aún es discutible pero pasará en la mayoría de las preguntas).

¡Mejor!

Answer 2

Esta pregunta es del concurso WEEK OF CODE 34 (HACKERRANK). Es un concurso en curso. No es justo discutir aquí ahora. Por favor, no hagas de quora una plataforma para tales actividades. Intenta hasta el final del concurso y si fallas, revisa los editoriales.

¡Feliz codificación!