Dada una array arr[] de N enteros positivos, la tarea es encontrar el MCM y el GCD mínimos entre los elementos de todas las sub-arrays posibles.
Ejemplos:
Entrada: arr[] = {4, 4, 8}
Salida: LCM = 4, GCD = 4
Todas las sub-arrays posibles son:
{4} -> LCM = 4, GCD = 4
{8} -> LCM = 8, GCD = 8
{4, 8} -> LCM = 8, GCD = 4
Entrada: arr[] = {2, 66, 14, 521}
Salida: LCM = 2, GCD = 1
Enfoque: Tenemos que abordar este problema con avidez. Es obvio que cuando disminuimos el número de elementos, el MCM se hará más pequeño y cuando aumentamos el número de elementos, el GCD se hará más pequeño. Entonces, tomaremos el elemento más pequeño de la array, que es un solo elemento y será el MCM requerido. Ahora, para GCD, el GCD mínimo será el GCD de todos los elementos de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return minimum GCD
// among all subarrays
int minGCD(int arr[], int n)
{
int minGCD = 0;
// Minimum GCD among all sub-arrays will be
// the GCD of all the elements of the array
for (int i = 0; i < n; i++)
minGCD = __gcd(minGCD, arr[i]);
return minGCD;
}
// Function to return minimum LCM
// among all subarrays
int minLCM(int arr[], int n)
{
int minLCM = arr[0];
// Minimum LCM among all sub-arrays will be
// the minimum element from the array
for (int i = 1; i < n; i++)
minLCM = min(minLCM, arr[i]);
return minLCM;
}
// Driver code
int main()
{
int arr[] = { 2, 66, 14, 521 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "LCM = " << minLCM(arr, n)
<< ", GCD = " << minGCD(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return minimum GCD
// among all subarrays
static int __gcd(int a, int b)
{
if (a == 0)
return b;
return __gcd(b % a, a);
}
static int minGCD(int arr[], int n)
{
int minGCD = 0;
// Minimum GCD among all sub-arrays will be
// the GCD of all the elements of the array
for (int i = 0; i < n; i++)
minGCD = __gcd(minGCD, arr[i]);
return minGCD;
}
// Function to return minimum LCM
// among all subarrays
static int minLCM(int arr[], int n)
{
int minLCM = arr[0];
// Minimum LCM among all sub-arrays will be
// the minimum element from the array
for (int i = 1; i < n; i++)
minLCM = Math.min(minLCM, arr[i]);
return minLCM;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 66, 14, 521 };
int n = arr.length;
System.out.println("LCM = " + minLCM(arr, n)
+ " GCD = "+minGCD(arr, n));
}
}
// This code is contributed by Code_Mech.
Python3
# Python3 implementation of the approach
from math import gcd
# Function to return minimum GCD
# among all subarrays
def minGCD(arr, n) :
minGCD = 0;
# Minimum GCD among all sub-arrays
# will be the GCD of all the elements
# of the array
for i in range(n) :
minGCD = gcd(minGCD, arr[i]);
return minGCD;
# Function to return minimum LCM
# among all subarrays
def minLCM(arr, n) :
minLCM = arr[0];
# Minimum LCM among all sub-arrays
# will be the minimum element from
# the array
for i in range(1, n) :
minLCM = min(minLCM, arr[i]);
return minLCM;
# Driver code
if __name__ == "__main__" :
arr = [ 2, 66, 14, 521 ];
n = len(arr);
print("LCM = ", minLCM(arr, n),
", GCD =", minGCD(arr, n));
# This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return minimum GCD
// among all subarrays
static int __gcd(int a, int b)
{
if (a == 0)
return b;
return __gcd(b % a, a);
}
static int minGCD(int [] arr, int n)
{
int minGCD = 0;
// Minimum GCD among all sub-arrays
// will be the GCD of all the
// elements of the array
for (int i = 0; i < n; i++)
minGCD = __gcd(minGCD, arr[i]);
return minGCD;
}
// Function to return minimum LCM
// among all subarrays
static int minLCM(int [] arr, int n)
{
int minLCM = arr[0];
// Minimum LCM among all sub-arrays
// will be the minimum element from
// the array
for (int i = 1; i < n; i++)
minLCM = Math.Min(minLCM, arr[i]);
return minLCM;
}
// Driver code
public static void Main()
{
int [] arr = { 2, 66, 14, 521 };
int n = arr.Length;
Console.WriteLine("LCM = " + minLCM(arr, n) +
", GCD = " + minGCD(arr, n));
}
}
// This code is contributed by ihritik.
PHP
<?php
// PHP implementation of the approach
// Function to return minimum GCD
// among all subarrays
function __gcd($a, $b)
{
if ($a == 0)
return $b;
return __gcd($b % $a, $a);
}
function minGCD($arr, $n)
{
$minGCD = 0;
// Minimum GCD among all sub-arrays
// will be the GCD of all the
// elements of the array
for ($i = 0; $i < $n; $i++)
$minGCD = __gcd($minGCD,
$arr[$i]);
return $minGCD;
}
// Function to return minimum LCM
// among all subarrays
function minLCM($arr, $n)
{
$minLCM = $arr[0];
// Minimum LCM among all sub-arrays
// will be the minimum element from
// the array
for ($i = 1; $i < $n; $i++)
$minLCM = min($minLCM,
$arr[$i]);
return $minLCM;
}
// Driver code
$arr = array(2, 66, 14, 521 );
$n = sizeof($arr);
echo "LCM = " . minLCM($arr, $n) . ", ";
echo "GCD = " . minGCD($arr, $n);
// This code is contributed by ihritik.
?>
Javascript
<script>
// javascript implementation of the approach
// Function to return minimum GCD
// among all subarrays
function __gcd(a , b) {
if (a == 0)
return b;
return __gcd(b % a, a);
}
function minGCD(arr , n) {
var minGCD = 0;
// Minimum GCD among all sub-arrays will be
// the GCD of all the elements of the array
for (i = 0; i < n; i++)
minGCD = __gcd(minGCD, arr[i]);
return minGCD;
}
// Function to return minimum LCM
// among all subarrays
function minLCM(arr , n) {
var minLCM = arr[0];
// Minimum LCM among all sub-arrays will be
// the minimum element from the array
for (i = 1; i < n; i++)
minLCM = Math.min(minLCM, arr[i]);
return minLCM;
}
// Driver code
var arr = [ 2, 66, 14, 521 ];
var n = arr.length;
document.write("LCM = " + minLCM(arr, n) + " GCD = " + minGCD(arr, n));
// This code contributed by umadevi9616
</script>
Producción:
LCM = 2, GCD = 1
Complejidad de Tiempo: O(NlogN)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.