Dada una array de n números, encuentra el mcm de ella.
Input : {1, 2, 8, 3}
Output : 24
Input : {2, 7, 3, 9, 4}
Output : 252
Sabemos que 
la relación anterior solo es válida para dos números. 
La idea aquí es extender nuestra relación a más de 2 números. Digamos que tenemos una array arr[] que contiene n elementos cuyo LCM necesita ser calculado.
Los pasos principales de nuestro algoritmo son:
- Inicializar ans = arr[0].
- Iterar sobre todos los elementos de la array, es decir, desde i = 1 hasta i = n-1
En la i-ésima iteración ans = LCM(arr[0], arr[1], …….., arr[i-1]). Esto se puede hacer fácilmente como LCM(arr[0], arr[1], …., arr[i]) = LCM(ans, arr[i]) . Por lo tanto, en la i-ésima iteración solo tenemos que hacer ans = LCM(ans, arr[i]) = ans x arr[i] / mcd(ans, arr[i])
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ program to find LCM of n elements
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Utility function to find
// GCD of 'a' and 'b'
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Returns LCM of array elements
ll findlcm(int arr[], int n)
{
// Initialize result
ll ans = arr[0];
// ans contains LCM of arr[0], ..arr[i]
// after i'th iteration,
for (int i = 1; i < n; i++)
ans = (((arr[i] * ans)) /
(gcd(arr[i], ans)));
return ans;
}
// Driver Code
int main()
{
int arr[] = { 2, 7, 3, 9, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%lld", findlcm(arr, n));
return 0;
}
Java
// Java Program to find LCM of n elements
public class GFG {
public static long lcm_of_array_elements(int[] element_array)
{
long lcm_of_array_elements = 1;
int divisor = 2;
while (true) {
int counter = 0;
boolean divisible = false;
for (int i = 0; i < element_array.length; i++) {
// lcm_of_array_elements (n1, n2, ... 0) = 0.
// For negative number we convert into
// positive and calculate lcm_of_array_elements.
if (element_array[i] == 0) {
return 0;
}
else if (element_array[i] < 0) {
element_array[i] = element_array[i] * (-1);
}
if (element_array[i] == 1) {
counter++;
}
// Divide element_array by devisor if complete
// division i.e. without remainder then replace
// number with quotient; used for find next factor
if (element_array[i] % divisor == 0) {
divisible = true;
element_array[i] = element_array[i] / divisor;
}
}
// If divisor able to completely divide any number
// from array multiply with lcm_of_array_elements
// and store into lcm_of_array_elements and continue
// to same divisor for next factor finding.
// else increment divisor
if (divisible) {
lcm_of_array_elements = lcm_of_array_elements * divisor;
}
else {
divisor++;
}
// Check if all element_array is 1 indicate
// we found all factors and terminate while loop.
if (counter == element_array.length) {
return lcm_of_array_elements;
}
}
}
// Driver Code
public static void main(String[] args)
{
int[] element_array = { 2, 7, 3, 9, 4 };
System.out.println(lcm_of_array_elements(element_array));
}
}
// Code contributed by Mohit Gupta_OMG
Python
# Python Program to find LCM of n elements def find_lcm(num1, num2): if(num1>num2): num = num1 den = num2 else: num = num2 den = num1 rem = num % den while(rem != 0): num = den den = rem rem = num % den gcd = den lcm = int(int(num1 * num2)/int(gcd)) return lcm l = [2, 7, 3, 9, 4] num1 = l[0] num2 = l[1] lcm = find_lcm(num1, num2) for i in range(2, len(l)): lcm = find_lcm(lcm, l[i]) print(lcm) # Code contributed by Mohit Gupta_OMG
C#
// C# Program to find LCM of n elements
using System;
public class GFG {
public static long lcm_of_array_elements(int[] element_array)
{
long lcm_of_array_elements = 1;
int divisor = 2;
while (true) {
int counter = 0;
bool divisible = false;
for (int i = 0; i < element_array.Length; i++) {
// lcm_of_array_elements (n1, n2, ... 0) = 0.
// For negative number we convert into
// positive and calculate lcm_of_array_elements.
if (element_array[i] == 0) {
return 0;
}
else if (element_array[i] < 0) {
element_array[i] = element_array[i] * (-1);
}
if (element_array[i] == 1) {
counter++;
}
// Divide element_array by devisor if complete
// division i.e. without remainder then replace
// number with quotient; used for find next factor
if (element_array[i] % divisor == 0) {
divisible = true;
element_array[i] = element_array[i] / divisor;
}
}
// If divisor able to completely divide any number
// from array multiply with lcm_of_array_elements
// and store into lcm_of_array_elements and continue
// to same divisor for next factor finding.
// else increment divisor
if (divisible) {
lcm_of_array_elements = lcm_of_array_elements * divisor;
}
else {
divisor++;
}
// Check if all element_array is 1 indicate
// we found all factors and terminate while loop.
if (counter == element_array.Length) {
return lcm_of_array_elements;
}
}
}
// Driver Code
public static void Main()
{
int[] element_array = { 2, 7, 3, 9, 4 };
Console.Write(lcm_of_array_elements(element_array));
}
}
// This Code is contributed by nitin mittal
PHP
<?php
// PHP program to find LCM of n elements
// Utility function to find
// GCD of 'a' and 'b'
function gcd($a, $b)
{
if ($b == 0)
return $a;
return gcd($b, $a % $b);
}
// Returns LCM of array elements
function findlcm($arr, $n)
{
// Initialize result
$ans = $arr[0];
// ans contains LCM of
// arr[0], ..arr[i]
// after i'th iteration,
for ($i = 1; $i < $n; $i++)
$ans = ((($arr[$i] * $ans)) /
(gcd($arr[$i], $ans)));
return $ans;
}
// Driver Code
$arr = array(2, 7, 3, 9, 4 );
$n = sizeof($arr);
echo findlcm($arr, $n);
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// Javascript program to find LCM of n elements
// Utility function to find
// GCD of 'a' and 'b'
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Returns LCM of array elements
function findlcm(arr, n)
{
// Initialize result
let ans = arr[0];
// ans contains LCM of arr[0], ..arr[i]
// after i'th iteration,
for (let i = 1; i < n; i++)
ans = (((arr[i] * ans)) /
(gcd(arr[i], ans)));
return ans;
}
// Driver Code
let arr = [ 2, 7, 3, 9, 4 ];
let n = arr.length;
document.write(findlcm(arr, n));
// This code is contributed by Mayank Tyagi
</script>
Producción
252
Complejidad de tiempo: O(n * log(min(a, b))), donde n representa el tamaño de la array dada.
Espacio auxiliar: O(n*log(min(a, b))) debido al espacio de pila recursivo.
A continuación se muestra la implementación del algoritmo anterior de forma recursiva:
C++
#include <bits/stdc++.h>
using namespace std;
//recursive implementation
int LcmOfArray(vector<int> arr, int idx){
// lcm(a,b) = (a*b/gcd(a,b))
if (idx == arr.size()-1){
return arr[idx];
}
int a = arr[idx];
int b = LcmOfArray(arr, idx+1);
return (a*b/__gcd(a,b)); // __gcd(a,b) is inbuilt library function
}
int main() {
vector<int> arr = {1,2,8,3};
cout << LcmOfArray(arr, 0) << "\n";
arr = {2,7,3,9,4};
cout << LcmOfArray(arr,0) << "\n";
return 0;
}
Java
import java.util.*;
class GFG
{
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
// recursive implementation
static int LcmOfArray(int[] arr, int idx)
{
// lcm(a,b) = (a*b/gcd(a,b))
if (idx == arr.length - 1){
return arr[idx];
}
int a = arr[idx];
int b = LcmOfArray(arr, idx+1);
return (a*b/__gcd(a,b)); //
}
public static void main(String[] args)
{
int[] arr = {1,2,8,3};
System.out.print(LcmOfArray(arr, 0)+ "\n");
int[] arr1 = {2,7,3,9,4};
System.out.print(LcmOfArray(arr1,0)+ "\n");
}
}
// This code is contributed by gauravrajput1
Python3
def __gcd(a, b): if (a == 0): return b return __gcd(b % a, a) # recursive implementation def LcmOfArray(arr, idx): # lcm(a,b) = (a*b/gcd(a,b)) if (idx == len(arr)-1): return arr[idx] a = arr[idx] b = LcmOfArray(arr, idx+1) return int(a*b/__gcd(a,b)) # __gcd(a,b) is inbuilt library function arr = [1,2,8,3] print(LcmOfArray(arr, 0)) arr = [2,7,3,9,4] print(LcmOfArray(arr,0)) # This code is contributed by divyeshrabadiya07.
C#
using System;
class GFG {
// Function to return
// gcd of a and b
static int __gcd(int a, int b)
{
if (a == 0)
return b;
return __gcd(b % a, a);
}
//recursive implementation
static int LcmOfArray(int[] arr, int idx){
// lcm(a,b) = (a*b/gcd(a,b))
if (idx == arr.Length-1){
return arr[idx];
}
int a = arr[idx];
int b = LcmOfArray(arr, idx+1);
return (a*b/__gcd(a,b)); // __gcd(a,b) is inbuilt library function
}
static void Main() {
int[] arr = {1,2,8,3};
Console.WriteLine(LcmOfArray(arr, 0));
int[] arr1 = {2,7,3,9,4};
Console.WriteLine(LcmOfArray(arr1,0));
}
}
Javascript
<script>
// Function to return
// gcd of a and b
function __gcd(a, b)
{
if (a == 0)
return b;
return __gcd(b % a, a);
}
//recursive implementation
function LcmOfArray(arr, idx){
// lcm(a,b) = (a*b/gcd(a,b))
if (idx == arr.length-1){
return arr[idx];
}
let a = arr[idx];
let b = LcmOfArray(arr, idx+1);
return (a*b/__gcd(a,b)); // __gcd(a,b) is inbuilt library function
}
let arr = [1,2,8,3];
document.write(LcmOfArray(arr, 0) + "</br>");
arr = [2,7,3,9,4];
document.write(LcmOfArray(arr,0));
// This code is contributed by decode2207.
</script>
Producción
24 252
Complejidad de tiempo: O(n * log(max(a, b)), donde n representa el tamaño de la array dada.
Espacio auxiliar: O(n) debido al espacio de pila recursivo.
Artículo relacionado :
- Encontrar MCM de más de dos (o arreglos) números sin usar GCD
- Función incorporada para calcular LCM en C++
Este artículo es una contribución de Madhur Modi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA