Número más pequeño para multiplicar para convertir punto flotante a natural

Dado un número de punto flotante positivo n , la tarea es encontrar el entero más pequeño k, tal que cuando multiplicamos k con n, obtengamos un número natural.
Ejemplos: 
 

Input : 30.25
Output : 4
30.25 * 4 = 321, there is no number less than 4
which can convert 30.25 into natural number.

Input : 5.5
Output : 2
5.5 * 2 = 11, there is no number less than 2
which can convert 5.5 into natural number.

Input : 5.33
Output : 100

La idea es convertir un número de punto flotante dado en una fracción (no necesariamente en forma reducida) y encontrar el MCD del numerador y el denominador. Por ejemplo, si el número de punto flotante de entrada es 30,25, lo convertimos en fracción como 3025/100. Esto se puede hacer fácilmente encontrando la posición del punto. 
Finalmente, para obtener la respuesta, dividimos el denominador de la fracción convertida por MCD del denominador y el numerador. Por ejemplo, GCD de 3025 y 100 es 25. Dividimos 100 entre 25 y obtenemos la respuesta como 4.
A continuación se muestra la implementación de este enfoque: 
 

// C++ program to find the smallest number to multiply
// to convert a floating point number into natural number.
#include<bits/stdc++.h>
using namespace std;
 
// Finding GCD of two number
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a%b);
}
 
// Returns smallest integer k such that k * str becomes
// natural. str is an input floating point number
int findnum(string &str)
{
    // Find size of string representing a
    // floating point number.
    int n = str.length();
 
    // Below is used to find denominator in
    // fraction form.
    int count_after_dot = 0;
 
    // Used to find value of count_after_dot
    bool dot_seen = false;
 
    // To find numerator in fraction form of
    // given number. For example, for 30.25,
    // numerator would be 3025.
    int num = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[i] != '.')
        {
            num = num*10 + (str[i] - '0');
            if (dot_seen == true)
                count_after_dot++;
        }
        else
            dot_seen = true;
    }
 
    // If there was no dot, then number
    // is already a natural.
    if (dot_seen == false)
    return 1;
 
    // Find denominator in fraction form. For example,
    // for 30.25, denominator is 100
    int dem = (int)pow(10, count_after_dot);
 
    // Result is denominator divided by
    // GCD-of-numerator-and-denominator. For example, for
    // 30.25, result is 100 / GCD(3025,100) = 100/25 = 4
    return (dem / gcd(num, dem));
}
 
// Driven Program
int main()
{
    string str = "5.125";
    cout << findnum(str) << endl;
    return 0;
}

// Java program to find the smallest number to multiply
// to convert a floating point number into natural number.
class GFG {
  // Finding GCD of two number
  static int gcd(int a, int b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
 
  // Returns smallest integer k such that k * str becomes
  // natural. str is an input floating point number
  static int findnum(String str) {
    // Find size of string representing a
    // floating point number.
    int n = str.length();
 
    // Below is used to find denominator in
    // fraction form.
    int count_after_dot = 0;
 
    // Used to find value of count_after_dot
    boolean dot_seen = false;
 
    // To find numerator in fraction form of
    // given number. For example, for 30.25,
    // numerator would be 3025.
    int num = 0;
    for (int i = 0; i < n; i++) {
      if (str.charAt(i) != '.') {
        num = num * 10 + (str.charAt(i) - '0');
        if (dot_seen == true)
          count_after_dot++;
      } else
        dot_seen = true;
    }
 
    // If there was no dot, then number
    // is already a natural.
    if (dot_seen == false)
      return 1;
 
    // Find denominator in fraction form. For example,
    // for 30.25, denominator is 100
    int dem = (int)Math.pow(10, count_after_dot);
 
    // Result is denominator divided by
    // GCD-of-numerator-and-denominator. For example, for
    // 30.25, result is 100 / GCD(3025, 100) = 100/25 = 4
    return (dem / gcd(num, dem));
  }
 
  // Driver code
  public static void main(String[] args) {
    String str = "5.125";
    System.out.print(findnum(str));
  }
}
// This code is contributed by Anant Agarwal.

# Python program to find the smallest number to multiply
# to convert a floating point number into natural number.
# Finding GCD of two number
import math
def gcd(a, b):
 
    if (b == 0):
        return a
    return gcd(b, a%b)
  
# Returns smallest integer k such that k * str becomes
# natural. str is an input floating point number
def findnum(str):
     
    # Find size of string representing a
    # floating point number.
    n = len(str)
    # Below is used to find denominator in
    # fraction form.
    count_after_dot = 0
  
    # Used to find value of count_after_dot
    dot_seen = 0
  
    # To find numerator in fraction form of
    # given number. For example, for 30.25,
    # numerator would be 3025.
    num = 0
    for i in range(n):
        if (str[i] != '.'):
            num = num*10 + int(str[i])
            if (dot_seen == 1):
                count_after_dot += 1
        else:
            dot_seen = 1
  
    # If there was no dot, then number
    # is already a natural.
    if (dot_seen == 0):
       return 1
  
    # Find denominator in fraction form. For example,
    # for 30.25, denominator is 100
    dem = int(math.pow(10, count_after_dot))
  
    # Result is denominator divided by
    # GCD-of-numerator-and-denominator. For example, for
    # 30.25, result is 100 / GCD(3025,100) = 100/25 = 4
    return (dem // gcd(num, dem))
  
# Driver Program
 
str = "5.125"
print (findnum(str))
 
# Contributed by: Afzal Ansari

// C# program to find the smallest
// number to multiply to convert a
// floating point number into
// natural number.
using System;
 
class GFG {
     
// Finding GCD of two number
static int gcd(int a, int b)
{
    if (b == 0)
    return a;
    return gcd(b, a % b);
}
 
// Returns smallest integer k
// such that k * str becomes
// natural. str is an input
// floating point number
static int findnum(String str)
{
 
    // Find size of string representing
    // a floating point number.
    int n = str.Length;
 
    // Below is used to find denominator
    // in fraction form.
    int count_after_dot = 0;
 
    // Used to find value of count_after_dot
    bool dot_seen = false;
 
    // To find numerator in fraction form of
    // given number. For example, for 30.25,
    // numerator would be 3025.
    int num = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[i] != '.')
        {
            num = num * 10 + (str[i] - '0');
            if (dot_seen == true)
            count_after_dot++;
        }
        else
            dot_seen = true;
    }
 
    // If there was no dot, then
    // number is already a natural.
    if (dot_seen == false)
    return 1;
 
    // Find denominator in fraction form.
    // For example, for 30.25,
    // denominator is 100
    int dem = (int)Math.Pow(10, count_after_dot);
 
    // Result is denominator divided by
    // GCD-of-numerator-and-denominator.
    // For example, for 30.25, result is
    // 100 / GCD(3025, 100) = 100/25 = 4
    return (dem / gcd(num, dem));
}
 
// Driver code
public static void Main()
{
    String str = "5.125";
    Console.Write(findnum(str));
}
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to find the smallest
// number to multiply to convert a
// floating point number into
// natural number.
 
// Finding GCD of two number
function gcd($a, $b)
{
    if ($b == 0)
        return $a;
    return gcd($b, $a % $b);
}
 
// Returns smallest integer k
// such that k * str becomes
// natural. str is an input
// floating point number
function findnum( $str)
{
     
    // Find size of string
    // representing a floating
    // point number.
    $n = strlen($str);
 
    // Below is used to
    // find denominator in
    // fraction form.
    $count_after_dot = 0;
 
    // Used to find value
    // of count_after_dot
    $dot_seen = false;
 
    // To find numerator in
    // fraction form of
    // given number. For
    // example, for 30.25,
    // numerator would be 3025.
    $num = 0;
    for($i = 0; $i < $n; $i++)
    {
        if ($str[$i] != '.')
        {
            $num = $num*10 + ($str[$i] - '0');
            if ($dot_seen == true)
                $count_after_dot++;
        }
        else
            $dot_seen = true;
    }
 
    // If there was no dot,
    // then number is
    // already a natural.
    if ($dot_seen == false)
    return 1;
 
    // Find denominator in
    // fraction form. For
    // example, for 30.25,
    // denominator is 100
    $dem = pow(10, $count_after_dot);
 
    // Result is denominator
    // divided by GCD-of-
    // numerator-and-denominator.
    // For example, for 30.25,
    // result is 100 / GCD(3025,100)
    // = 100/25 = 4
    return ($dem / gcd($num, $dem));
}
 
// Driver Code
{
    $str = "5.125";
    echo findnum($str) ;
    return 0;
}
 
// This code is contributed by nitin mittal
?>

<script>
// javascript program to find the smallest number to multiply
// to convert a floating point number into natural number.
 
    // Finding GCD of two number
    function gcd(a , b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
 
    // Returns smallest integer k such that k * str becomes
    // natural. str is an input floating point number
    function findnum( str)
    {
     
        // Find size of string representing a
        // floating point number.
        var n = str.length;
 
        // Below is used to find denominator in
        // fraction form.
        var count_after_dot = 0;
 
        // Used to find value of count_after_dot
        let dot_seen = false;
 
        // To find numerator in fraction form of
        // given number. For example, for 30.25,
        // numerator would be 3025.
        var num = 0;
        for (i = 0; i < n; i++) {
            if (str.charAt(i) != '.') {
                num = num * 10 + (str.charAt(i) - '0');
                if (dot_seen == true)
                    count_after_dot++;
            } else
                dot_seen = true;
        }
 
        // If there was no dot, then number
        // is already a natural.
        if (dot_seen == false)
            return 1;
 
        // Find denominator in fraction form. For example,
        // for 30.25, denominator is 100
        var dem = parseInt( Math.pow(10, count_after_dot));
 
        // Result is denominator divided by
        // GCD-of-numerator-and-denominator. For example, for
        // 30.25, result is 100 / GCD(3025, 100) = 100/25 = 4
        return (dem / gcd(num, dem));
    }
 
    // Driver code   
    let str = "5.125";
    document.write(findnum(str));
 
// This code is contributed by todaysgaurav
</script>

Producción: 
 

8

Complejidad de tiempo: O(n) 
Espacio auxiliar: O(log(min(a,b)))

Este artículo es una contribución de Aarti_Rathi y Anuj Chauhan(anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.