Dada una array arr[] de tamaño N , la tarea es encontrar el MCM (Mínimo Común Múltiple) mínimo de todos los pares únicos en la array dada, donde 1 <= N <= 10 5 , 1 <= arr[i] < = 10 5 .
Ejemplos:
Entrada: arr[] = {2, 4, 3}
Salida: 4
Explicación
LCM (2, 4) = 4
LCM (2, 3) = 6
LCM (4, 3) = 12
El mínimo posible LCM es 4.Entrada: array [] ={1, 5, 2, 2, 6}
Salida: 2
Enfoque ingenuo
- Genere todos los pares posibles y calcule LCM para cada par único.
- Encuentre el MCM mínimo de todos los pares únicos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find
// minimum possible lcm
// from any pair
#include <bits/stdc++.h>
using namespace std;
// function to compute
// GCD of two numbers
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// function that return
// minimum possible lcm
// from any pair
int minLCM(int arr[], int n)
{
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
// fix the ith element and
// iterate over all the array
// to find minimum LCM
for (int j = i + 1; j < n; j++) {
int g = gcd(arr[i], arr[j]);
int lcm = arr[i] / g * arr[j];
ans = min(ans, lcm);
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 4, 3, 6, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minLCM(arr, n) << endl;
return 0;
}
Java
// Java program to find minimum
// possible lcm from any pair
import java.io.*;
import java.util.*;
class GFG {
// Function to compute
// GCD of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function that return minimum
// possible lcm from any pair
static int minLCM(int arr[], int n)
{
int ans = Integer.MAX_VALUE;
for(int i = 0; i < n; i++)
{
// Fix the ith element and
// iterate over all the array
// to find minimum LCM
for(int j = i + 1; j < n; j++)
{
int g = gcd(arr[i], arr[j]);
int lcm = arr[i] / g * arr[j];
ans = Math.min(ans, lcm);
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 4, 3, 6, 5 };
int n = arr.length;
System.out.println(minLCM(arr,n));
}
}
// This code is contributed by coder001
Python3
# Python3 program to find minimum # possible lcm from any pair import sys # Function to compute # GCD of two numbers def gcd(a, b): if (b == 0): return a; return gcd(b, a % b); # Function that return minimum # possible lcm from any pair def minLCM(arr, n): ans = 1000000000; for i in range(n): # Fix the ith element and # iterate over all the # array to find minimum LCM for j in range(i + 1, n): g = gcd(arr[i], arr[j]); lcm = arr[i] / g * arr[j]; ans = min(ans, lcm); return ans; # Driver code arr = [ 2, 4, 3, 6, 5 ]; print(minLCM(arr, 5)) # This code is contributed by grand_master
C#
// C# program to find minimum
// possible lcm from any pair
using System;
class GFG{
// Function to compute
// GCD of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function that return minimum
// possible lcm from any pair
static int minLCM(int []arr, int n)
{
int ans = Int32.MaxValue;
for(int i = 0; i < n; i++)
{
// Fix the ith element and
// iterate over all the array
// to find minimum LCM
for(int j = i + 1; j < n; j++)
{
int g = gcd(arr[i], arr[j]);
int lcm = arr[i] / g * arr[j];
ans = Math.Min(ans, lcm);
}
}
return ans;
}
// Driver code
public static void Main()
{
int []arr = { 2, 4, 3, 6, 5 };
int n = arr.Length;
Console.Write(minLCM(arr,n));
}
}
// This code is contributed by Akanksha_Rai
Javascript
<script>
// Javascript program to find
// minimum possible lcm
// from any pair
// function to compute
// GCD of two numbers
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// function that return
// minimum possible lcm
// from any pair
function minLCM(arr, n)
{
let ans = Number.MAX_VALUE;
for (let i = 0; i < n; i++) {
// fix the ith element and
// iterate over all the array
// to find minimum LCM
for (let j = i + 1; j < n; j++) {
let g = gcd(arr[i], arr[j]);
let lcm = arr[i] / g * arr[j];
ans = Math.min(ans, lcm);
}
}
return ans;
}
let arr = [ 2, 4, 3, 6, 5 ];
let n = arr.length;
document.write(minLCM(arr, n));
</script>
Producción:
4
Complejidad del tiempo: O(N 2 )
Enfoque eficiente: este enfoque depende de la fórmula:
Producto de dos números = MCM de dos números * MCD de dos números
- En la fórmula de MCM, el denominador es el MCD de dos números, y el MCD de dos números nunca será mayor que el número mismo.
- Entonces, para un GCD fijo, encuentre los dos múltiplos más pequeños de ese GCD fijo que está presente en la array dada.
- Almacene solo los dos múltiplos más pequeños de cada GCD porque elegir un múltiplo más grande de GCD que esté presente en la array, sin importar qué, nunca dará la respuesta mínima.
- Finalmente, use un tamiz para encontrar el número mínimo de dos que es el múltiplo del GCD elegido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// pair having minimum LCM
#include <bits/stdc++.h>
using namespace std;
// function that return
// pair having minimum LCM
int minLCM(int arr[], int n)
{
int mx = 0;
for (int i = 0; i < n; i++) {
// find max element in the array as
// the gcd of two elements from the
// array can't greater than max element.
mx = max(mx, arr[i]);
}
// created a 2D array to store minimum
// two multiple of any particular i.
vector<vector<int> > mul(mx + 1);
for (int i = 0; i < n; i++) {
if (mul[arr[i]].size() > 1) {
// we already found two
// smallest multiple
continue;
}
mul[arr[i]].push_back(arr[i]);
}
// iterating over all gcd
for (int i = 1; i <= mx; i++) {
// iterating over its multiple
for (int j = i + i; j <= mx; j += i) {
if (mul[i].size() > 1) {
// if we already found the
// two smallest multiple of i
break;
}
for (int k : mul[j]) {
if (mul[i].size() > 1)
break;
mul[i].push_back(k);
}
}
}
int ans = INT_MAX;
for (int i = 1; i <= mx; i++) {
if (mul[i].size() <= 1)
continue;
// choosing smallest two multiple
int a = mul[i][0], b = mul[i][1];
// calculating lcm
int lcm = (a * b) / i;
ans = min(ans, lcm);
}
// return final answer
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 4, 3, 6, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minLCM(arr, n) << endl;
return 0;
}
Java
// Java program to find the
// pair having minimum LCM
import java.util.Vector;
class GFG{
// Function that return
// pair having minimum LCM
static int minLCM(int arr[],
int n)
{
int mx = 0;
for (int i = 0; i < n; i++)
{
// Find max element in the
// array as the gcd of two
// elements from the array
// can't greater than max element.
mx = Math.max(mx, arr[i]);
}
// Created a 2D array to store minimum
// two multiple of any particular i.
Vector<Integer> []mul = new Vector[mx + 1];
for (int i = 0; i < mul.length; i++)
mul[i] = new Vector<Integer>();
for (int i = 0; i < n; i++)
{
if (mul[arr[i]].size() > 1)
{
// We already found two
// smallest multiple
continue;
}
mul[arr[i]].add(arr[i]);
}
// Iterating over all gcd
for (int i = 1; i <= mx; i++)
{
// Iterating over its multiple
for (int j = i + i; j <= mx; j += i)
{
if (mul[i].size() > 1)
{
// If we already found the
// two smallest multiple of i
break;
}
for (int k : mul[j])
{
if (mul[i].size() > 1)
break;
mul[i].add(k);
}
}
}
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= mx; i++)
{
if (mul[i].size() <= 1)
continue;
// Choosing smallest
// two multiple
int a = mul[i].get(0),
b = mul[i].get(1);
// Calculating lcm
int lcm = (a * b) / i;
ans = Math.min(ans, lcm);
}
// Return final answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {2, 4, 3, 6, 5};
int n = arr.length;
System.out.print(minLCM(arr, n) + "\n");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to find the # pair having minimum LCM import sys # function that return # pair having minimum LCM def minLCM(arr, n) : mx = 0 for i in range(n) : # find max element in the array as # the gcd of two elements from the # array can't greater than max element. mx = max(mx, arr[i]) # created a 2D array to store minimum # two multiple of any particular i. mul = [[] for i in range(mx + 1)] for i in range(n) : if (len(mul[arr[i]]) > 1) : # we already found two # smallest multiple continue mul[arr[i]].append(arr[i]) # iterating over all gcd for i in range(1, mx + 1) : # iterating over its multiple for j in range(i + i, mx + 1, i) : if (len(mul[i]) > 1) : # if we already found the # two smallest multiple of i break for k in mul[j] : if (len(mul[i]) > 1) : break mul[i].append(k) ans = sys.maxsize for i in range(1, mx + 1) : if (len(mul[i]) <= 1) : continue # choosing smallest two multiple a, b = mul[i][0], mul[i][1] # calculating lcm lcm = (a * b) // i ans = min(ans, lcm) # return final answer return ans # Driver code arr = [ 2, 4, 3, 6, 5 ] n = len(arr) print(minLCM(arr, n)) # This code is contributed by divyesh072019
C#
// C# program to find the
// pair having minimum LCM
using System;
using System.Collections.Generic;
class GFG{
// Function that return
// pair having minimum LCM
static int minLCM(int []arr,
int n)
{
int mx = 0;
for (int i = 0; i < n; i++)
{
// Find max element in the
// array as the gcd of two
// elements from the array
// can't greater than max element.
mx = Math.Max(mx, arr[i]);
}
// Created a 2D array to store minimum
// two multiple of any particular i.
List<int> []mul = new List<int>[mx + 1];
for (int i = 0; i < mul.Length; i++)
mul[i] = new List<int>();
for (int i = 0; i < n; i++)
{
if (mul[arr[i]].Count > 1)
{
// We already found two
// smallest multiple
continue;
}
mul[arr[i]].Add(arr[i]);
}
// Iterating over all gcd
for (int i = 1; i <= mx; i++)
{
// Iterating over its multiple
for (int j = i + i; j <= mx; j += i)
{
if (mul[i].Count > 1)
{
// If we already found the
// two smallest multiple of i
break;
}
foreach (int k in mul[j])
{
if (mul[i].Count > 1)
break;
mul[i].Add(k);
}
}
}
int ans = int.MaxValue;
for (int i = 1; i <= mx; i++)
{
if (mul[i].Count <= 1)
continue;
// Choosing smallest
// two multiple
int a = mul[i][0],
b = mul[i][1];
// Calculating lcm
int lcm = (a * b) / i;
ans = Math.Min(ans, lcm);
}
// Return readonly answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {2, 4, 3, 6, 5};
int n = arr.Length;
Console.Write(minLCM(arr, n) + "\n");
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to find the
// pair having minimum LCM
// function that return
// pair having minimum LCM
function minLCM(arr, n)
{
var mx = 0;
for(var i = 0; i < n; i++)
{
// Find max element in the array as
// the gcd of two elements from the
// array can't greater than max element.
mx = Math.max(mx, arr[i]);
}
// Created a 2D array to store minimum
// two multiple of any particular i.
var mul = Array.from(Array(mx + 1), () => Array());
for(var i = 0; i < n; i++)
{
if (mul[arr[i]].length > 1)
{
// We already found two
// smallest multiple
continue;
}
mul[arr[i]].push(arr[i]);
}
// Iterating over all gcd
for(var i = 1; i <= mx; i++)
{
// Iterating over its multiple
for(var j = i + i; j <= mx; j += i)
{
if (mul[i].length > 1)
{
// If we already found the
// two smallest multiple of i
break;
}
mul[j].forEach(k => {
if (mul[i].length <= 1)
{
mul[i].push(k);
}
});
}
}
var ans = 1000000000;
for(var i = 1; i <= mx; i++)
{
if (mul[i].length <= 1)
continue;
// Choosing smallest two multiple
var a = mul[i][0], b = mul[i][1];
// Calculating lcm
var lcm = (a * b) / i;
ans = Math.min(ans, lcm);
}
// Return final answer
return ans;
}
// Driver code
var arr = [ 2, 4, 3, 6, 5 ];
var n = arr.length;
document.write( minLCM(arr, n) + "<br>");
// This code is contributed by itsok
</script>
Producción:
4
Complejidad de tiempo: O((N + M) * log(M))
Espacio auxiliar: O(M) donde M es el elemento máximo de la array.
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA