Dado el Numerador y el Denominador de N fracciones. La tarea es encontrar el producto de N fracciones y generar la respuesta en forma reducida.
Ejemplos:
Input : N = 3
num[] = { 1, 2, 5 }
den[] = { 2, 1, 6 }
Output : 5/6
Product of 1/2 * 2/1 * 5/6 is 10/12.
Reduced form of 10/12 is 5/6.
Input : N = 4
num[] = { 1, 2, 5, 9 }
den[] = { 2, 1, 6, 27 }
Output : 5/18
La idea es encontrar el producto de Numerator en una variable, digamos new_num. Ahora, encuentra el producto del Denominador en otra variable, digamos new_den.
Ahora, para encontrar la respuesta en forma reducida, encuentre el máximo común divisor de new_num y new_den y divida new_num y new_den por el MCD calculado.
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to find product of N
// fractions in reduced form.
#include <bits/stdc++.h>
using namespace std;
// Function to return gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Print the Product of N fraction in Reduced Form.
void productReduce(int n, int num[], int den[])
{
int new_num = 1, new_den = 1;
// finding the product of all N
// numerators and denominators.
for (int i = 0; i < n; i++) {
new_num *= num[i];
new_den *= den[i];
}
// Finding GCD of new numerator and
// denominator
int GCD = gcd(new_num, new_den);
// Converting into reduced form.
new_num /= GCD;
new_den /= GCD;
cout << new_num << "/" << new_den << endl;
}
// Driven Program
int main()
{
int n = 3;
int num[] = { 1, 2, 5 };
int den[] = { 2, 1, 6 };
productReduce(n, num, den);
return 0;
}
Java
// Java program to find product of N
// fractions in reduced form.
import java.io.*;
class GFG {
// Function to return gcd of a and b
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Print the Product of N fraction in
// Reduced Form.
static void productReduce(int n, int num[],
int den[])
{
int new_num = 1, new_den = 1;
// finding the product of all N
// numerators and denominators.
for (int i = 0; i < n; i++) {
new_num *= num[i];
new_den *= den[i];
}
// Finding GCD of new numerator and
// denominator
int GCD = gcd(new_num, new_den);
// Converting into reduced form.
new_num /= GCD;
new_den /= GCD;
System.out.println(new_num + "/" +new_den);
}
// Driven Program
public static void main (String[] args) {
int n = 3;
int num[] = { 1, 2, 5 };
int den[] = { 2, 1, 6 };
productReduce(n, num, den);
}
}
//This code is contributed by vt_m.
Python3
# Python3 program to find # product of N fractions # in reduced form. # Function to return # gcd of a and b def gcd(a, b): if (a == 0): return b; return gcd(b % a, a); # Print the Product of N # fraction in Reduced Form. def productReduce(n, num, den): new_num = 1; new_den = 1; # finding the product # of all N numerators # and denominators. for i in range(n): new_num = new_num * num[i]; new_den = new_den * den[i]; # Finding GCD of # new numerator # and denominator GCD = gcd(new_num, new_den); # Converting into # reduced form. new_num = new_num / GCD; new_den = new_den / GCD; print(int(new_num), "/", int(new_den)); # Driver Code n = 3; num = [1, 2, 5]; den = [2, 1, 6]; productReduce(n, num, den); # This code is contributed # by mits
C#
// C# program to find product of N
// fractions in reduced form.
using System;
class GFG {
// Function to return gcd of a and b
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Print the Product of N fraction in
// Reduced Form.
static void productReduce(int n, int []num,
int []den)
{
int new_num = 1, new_den = 1;
// finding the product of all N
// numerators and denominators.
for (int i = 0; i < n; i++) {
new_num *= num[i];
new_den *= den[i];
}
// Finding GCD of new numerator and
// denominator
int GCD = gcd(new_num, new_den);
// Converting into reduced form.
new_num /= GCD;
new_den /= GCD;
Console.WriteLine(new_num + "/" +new_den);
}
// Driven Program
public static void Main () {
int n = 3;
int []num = { 1, 2, 5 };
int []den = { 2, 1, 6 };
productReduce(n, num, den);
}
}
//This code is contributed by vt_m.
PHP
<?php
// PHP program to find product of N
// fractions in reduced form.
// Function to return
// gcd of a and b
function gcd($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
// Print the Product of N
// fraction in Reduced Form.
function productReduce($n, $num, $den)
{
$new_num = 1; $new_den = 1;
// finding the product of all N
// numerators and denominators.
for ($i = 0; $i < $n; $i++)
{
$new_num *= $num[$i];
$new_den *= $den[$i];
}
// Finding GCD of new
// numerator and denominator
$GCD = gcd($new_num, $new_den);
// Converting into reduced form.
$new_num /= $GCD;
$new_den /= $GCD;
echo $new_num , "/" , $new_den ,"\n";
}
// Driver Code
$n = 3;
$num = array(1, 2, 5);
$den = array(2, 1, 6);
productReduce($n, $num, $den);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to find product of N
// fractions in reduced form.
// Function to return gcd of a and b
function gcd( a, b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Print the Product of N fraction in Reduced Form.
function productReduce( n, num , den)
{
let new_num = 1, new_den = 1;
// finding the product of all N
// numerators and denominators.
for (let i = 0; i < n; i++) {
new_num *= num[i];
new_den *= den[i];
}
// Finding GCD of new numerator and
// denominator
let GCD = gcd(new_num, new_den);
// Converting into reduced form.
new_num /= GCD;
new_den /= GCD;
document.write( new_num + "/" + new_den);
}
// Driven Program
let n = 3;
let num = [ 1, 2, 5 ];
let den = [ 2, 1, 6 ];
productReduce(n, num, den);
// This code contributed by aashish1995
</script>
Producción :
5/6
Complejidad de tiempo : O(n + log(min(a,b)))
Espacio auxiliar: O(log(min(a,b)))
¿Cómo evitar el desbordamiento?
La solución anterior provoca el desbordamiento de grandes números. Podemos evitar el desbordamiento encontrando primero los factores primos de todos los numeradores y denominadores. Una vez que hemos encontrado los factores primos, podemos cancelar los factores primos comunes.
Nota: cuando se le pide que represente la respuesta en forma de {P \times {Q} ^ {-1}} .
Para estas preguntas, primero convierta el numerador y el denominador en forma reducible P/Q como se explicó anteriormente. Luego, encuentre el inverso multiplicativo modular de Q con respecto a un número primo m (generalmente, 10 ^ 9 + 7) que se da en cuestión. Después de encontrar el inverso multiplicativo modular de Q, multiplíquelo con P y tome el módulo con el número primo m dado, lo que nos da la salida requerida.
// GraciasVaiBzZk por sugerir esta condición.
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.