HCF de array de fracciones (o números racionales)

Dada una serie de fracciones. Encuentra el HCF de una serie de fracciones dada. 
Ejemplos: 
 

Input : [{2, 5}, {8, 9}, {16, 81}, {10, 27}]
Output :  2, 405 
Explanation : 2/405 is the largest number that
divides all 2/5, 8/9, 16/81 and 10/27.

Input : [{9, 10}, {12, 25}, {18, 35}, {21, 40}]
Output : 3, 1400

Acercarse: 
 

Encuentra el HCF de los numeradores. 
Encuentra el MCM de los denominadores. 
Calcule la fracción de HCF/LCM 
Reduzca la fracción a la fracción más baja. 
 

C++

// CPP program to find HCF of array of
// rational numbers (fractions).
#include <iostream>
using namespace std;
 
// hcf of two number
int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return (gcd(b, a % b));
}
 
// find hcf of numerator series
int findHcf(int** arr, int size)
{
    int ans = arr[0][0];   
    for (int i = 1; i < size; i++)   
        ans = gcd(ans, arr[i][0]);
 
    // return hcf of numerator
    return (ans);
}
 
// find lcm of denominator series
int findLcm(int** arr, int size)
{
    // ans contains LCM of arr[0][1], ..arr[i][1]
    int ans = arr[0][1];
    for (int i = 1; i < size; i++)
        ans = (((arr[i][1] * ans)) /
               (gcd(arr[i][1], ans)));
 
    // return lcm of denominator
    return (ans);
}
 
// Core Function
int* hcfOfFraction(int** arr, int size)
{
    // found hcf of numerator
    int hcf_of_num = findHcf(arr, size);
 
    // found lcm of denominator
    int lcm_of_deno = findLcm(arr, size);
 
    int* result = new int[2];
    result[0] = hcf_of_num;
    result[1] = lcm_of_deno;
 
    for (int i = result[0] / 2; i > 1; i--)
    {
        if ((result[1] % i == 0) && (result[0] % i == 0))
        {
            result[1] /= i;
            result[0] /= i;
        }
    }
 
    // return result
    return (result);
}
 
// Main function
int main()
{
    int size = 4;
    int** arr = new int*[size];
 
    // Initialize the every row
    // with size 2 (1 for numerator
    // and 2 for denominator)
    for (int i = 0; i < size; i++)
        arr[i] = new int[2];
 
    arr[0][0] = 9;
    arr[0][1] = 10;
    arr[1][0] = 12;
    arr[1][1] = 25;
    arr[2][0] = 18;
    arr[2][1] = 35;
    arr[3][0] = 21;
    arr[3][1] = 40;
     
    // function for calculate the result
    int* result = hcfOfFraction(arr, size);
     
    // print the result
    cout << result[0] << ", " << result[1] << endl;
    return 0;
}

Java

// Java program to find HCF of array of
// rational numbers (fractions).
class GFG
{
 
// hcf of two number
static int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return (gcd(b, a % b));
}
 
// find hcf of numerator series
static int findHcf(int [][]arr, int size)
{
    int ans = arr[0][0];
    for (int i = 1; i < size; i++)
        ans = gcd(ans, arr[i][0]);
 
    // return hcf of numerator
    return (ans);
}
 
// find lcm of denominator series
static int findLcm(int[][] arr, int size)
{
    // ans contains LCM of arr[0][1], ..arr[i][1]
    int ans = arr[0][1];
    for (int i = 1; i < size; i++)
        ans = (((arr[i][1] * ans)) /
            (gcd(arr[i][1], ans)));
 
    // return lcm of denominator
    return (ans);
}
 
// Core Function
static int[] hcfOfFraction(int[][] arr, int size)
{
    // found hcf of numerator
    int hcf_of_num = findHcf(arr, size);
 
    // found lcm of denominator
    int lcm_of_deno = findLcm(arr, size);
 
    int[] result = new int[2];
    result[0] = hcf_of_num;
    result[1] = lcm_of_deno;
 
    for (int i = result[0] / 2; i > 1; i--)
    {
        if ((result[1] % i == 0) && (result[0] % i == 0))
        {
            result[1] /= i;
            result[0] /= i;
        }
    }
 
    // return result
    return (result);
}
 
// Driver code
public static void main(String[] args)
{
    int size = 4;
    int[][] arr = new int[size][size];
 
    // Initialize the every row
    // with size 2 (1 for numerator
    // and 2 for denominator)
    for (int i = 0; i < size; i++)
        arr[i] = new int[2];
 
    arr[0][0] = 9;
    arr[0][1] = 10;
    arr[1][0] = 12;
    arr[1][1] = 25;
    arr[2][0] = 18;
    arr[2][1] = 35;
    arr[3][0] = 21;
    arr[3][1] = 40;
     
    // function for calculate the result
    int[] result = hcfOfFraction(arr, size);
     
    // print the result
    System.out.println(result[0] + ", " + result[1]);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python 3 program to find HCF of array of
from math import gcd
 
# find hcf of numerator series
def findHcf(arr, size):
    ans = arr[0][0]
    for i in range(1, size, 1):
        ans = gcd(ans, arr[i][0])
 
    # return hcf of numerator
    return (ans)
 
# find lcm of denominator series
def findLcm(arr, size):
     
    # ans contains LCM of arr[0][1], ..arr[i][1]
    ans = arr[0][1]
    for i in range(1, size, 1):
        ans = int((((arr[i][1] * ans)) /
                (gcd(arr[i][1], ans))))
 
    # return lcm of denominator
    return (ans)
 
# Core Function
def hcfOfFraction(arr, size):
     
    # found hcf of numerator
    hcf_of_num = findHcf(arr, size)
 
    # found lcm of denominator
    lcm_of_deno = findLcm(arr, size)
 
    result = [0 for i in range(2)]
    result[0] = hcf_of_num
    result[1] = lcm_of_deno
 
    i = int(result[0] / 2)
    while(i > 1):
        if ((result[1] % i == 0) and
            (result[0] % i == 0)):
            result[1] = int(result[1] / i)
            result[0] = (result[0] / i)
 
    # return result
    return (result)
 
# Driver Code
if __name__ == '__main__':
    size = 4
    arr = [0 for i in range(size)]
 
    # Initialize the every row
    # with size 2 (1 for numerator
    # and 2 for denominator)
    for i in range(size):
        arr[i] = [0 for i in range(2)]
 
    arr[0][0] = 9
    arr[0][1] = 10
    arr[1][0] = 12
    arr[1][1] = 25
    arr[2][0] = 18
    arr[2][1] = 35
    arr[3][0] = 21
    arr[3][1] = 40
     
    # function for calculate the result
    result = hcfOfFraction(arr, size)
     
    # print the result
    print(result[0], ",", result[1])
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find HCF of array of
// rational numbers (fractions).
using System;
 
class GFG
{
 
// hcf of two number
static int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return (gcd(b, a % b));
}
 
// find hcf of numerator series
static int findHcf(int [,]arr, int size)
{
    int ans = arr[0, 0];
    for (int i = 1; i < size; i++)
        ans = gcd(ans, arr[i, 0]);
 
    // return hcf of numerator
    return (ans);
}
 
// find lcm of denominator series
static int findLcm(int[,] arr, int size)
{
    // ans contains LCM of arr[0,1], ..arr[i,1]
    int ans = arr[0,1];
    for (int i = 1; i < size; i++)
        ans = (((arr[i, 1] * ans)) /
            (gcd(arr[i, 1], ans)));
 
    // return lcm of denominator
    return (ans);
}
 
// Core Function
static int[] hcfOfFraction(int[,] arr, int size)
{
    // found hcf of numerator
    int hcf_of_num = findHcf(arr, size);
 
    // found lcm of denominator
    int lcm_of_deno = findLcm(arr, size);
 
    int[] result = new int[2];
    result[0] = hcf_of_num;
    result[1] = lcm_of_deno;
 
    for (int i = result[0] / 2; i > 1; i--)
    {
        if ((result[1] % i == 0) && (result[0] % i == 0))
        {
            result[1] /= i;
            result[0] /= i;
        }
    }
 
    // return result
    return (result);
}
 
// Driver code
public static void Main(String[] args)
{
    int size = 4;
    int[,] arr = new int[size, size];
 
    // Initialize the every row
    // with size 2 (1 for numerator
    // and 2 for denominator)
 
 
    arr[0, 0] = 9;
    arr[0, 1] = 10;
    arr[1, 0] = 12;
    arr[1, 1] = 25;
    arr[2, 0] = 18;
    arr[2, 1] = 35;
    arr[3, 0] = 21;
    arr[3, 1] = 40;
     
    // function for calculate the result
    int[] result = hcfOfFraction(arr, size);
     
    // print the result
    Console.WriteLine(result[0] + ", " + result[1]);
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
// Javascript program to find HCF of array of
// rational numbers (fractions).
 
// hcf of two number
function gcd(a,b)
{
    if (a % b == 0)
        return b;
    else
        return (gcd(b, a % b));
}
 
// find hcf of numerator series
function findHcf(arr,size)
{
    let ans = arr[0][0];
    for (let i = 1; i < size; i++)
        ans = gcd(ans, arr[i][0]);
   
    // return hcf of numerator
    return (ans);
}
 
// find lcm of denominator series
function findLcm(arr,size)
{
    // ans contains LCM of arr[0][1], ..arr[i][1]
    let ans = arr[0][1];
    for (let i = 1; i < size; i++)
        ans = Math.floor(((arr[i][1] * ans)) /
            (gcd(arr[i][1], ans)));
   
    // return lcm of denominator
    return (ans);
}
 
// Core Function
function hcfOfFraction(arr,size)
{
    // found hcf of numerator
    let hcf_of_num = findHcf(arr, size);
   
    // found lcm of denominator
    let lcm_of_deno = findLcm(arr, size);
   
    let result = new Array(2);
    result[0] = hcf_of_num;
    result[1] = lcm_of_deno;
   
    for (let i = result[0] / 2; i > 1; i--)
    {
        if ((result[1] % i == 0) && (result[0] % i == 0))
        {
            result[1] /= i;
            result[0] /= i;
        }
    }
   
    // return result
    return (result);
}
 
// Driver code
let size = 4;
let arr = new Array(size);
 
// Initialize the every row
// with size 2 (1 for numerator
// and 2 for denominator)
for (let i = 0; i < size; i++)
    arr[i] = new Array(2);
 
arr[0][0] = 9;
arr[0][1] = 10;
arr[1][0] = 12;
arr[1][1] = 25;
arr[2][0] = 18;
arr[2][1] = 35;
arr[3][0] = 21;
arr[3][1] = 40;
 
// function for calculate the result
let result = hcfOfFraction(arr, size);
 
// print the result
document.write(result[0] + ", " + result[1]+"<br>");
 
// This code is contributed by rag2127
</script>

Producción: 
 

3, 1400

Complejidad de tiempo: O(n log(a)), donde a es el elemento máximo en el arreglo
Espacio auxiliar: O(log(a)), donde a es el elemento máximo en el arreglo

 Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . 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 Amit_Soni 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 *