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>
LCM = 2, GCD = 1
Complejidad de Tiempo: O(NlogN)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.