LCM y GCD mínimos posibles entre todos los subconjuntos posibles

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.

Publicación traducida automáticamente

Artículo escrito por souradeep y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *