Encuentra una secuencia recurrente en una fracción

Dada una fracción, encuentre una secuencia recurrente de dígitos si existe, de lo contrario, imprima «Sin secuencia recurrente».

Ejemplos:

Input  : Numerator = 8, Denominator = 3
Output : Recurring sequence is 6 
Explanation : 8/3 = 2.66666666.......  

Input : Numerator = 50, Denominator = 22
Output : Recurring sequence is 27
Explanation : 50/22 = 2.272727272..... 

Input : Numerator = 11, Denominator = 2
Output : No recurring sequence
Explanation : 11/2 = 5.5

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

¿Cuándo se repite la parte fraccionaria?
Simulemos el proceso de convertir fracciones a decimales. Miremos la parte donde ya hemos descubierto la parte entera, que es piso (numerador/denominador). Ahora nos queda (resto = numerador% denominador) / denominador. 

Si recuerdas el proceso de conversión a decimal, en cada paso hacemos lo siguiente: 

1. Multiplica el resto por 10.
2. Agregue el resto/denominador al resultado.
3. Resto = resto % denominador.

En cualquier momento, si el resto se convierte en 0, hemos terminado.
Sin embargo, cuando hay una secuencia recurrente, el resto nunca se convierte en 0. Por ejemplo, si miras 1/3, el resto nunca se convierte en 0.

A continuación hay una observación importante: 
si comenzamos con el resto ‘rem’ y si el resto se repite en cualquier momento, los dígitos entre las dos apariciones de ‘rem’ se siguen repitiendo.
Entonces, la idea es almacenar los restos vistos en un mapa. Cada vez que se repite un resto, devolvemos la secuencia anterior a la siguiente aparición. 

A continuación se muestra la implementación de la idea anterior. 

// C++ program to find repeating
// sequence in a fraction
#include <bits/stdc++.h>
using namespace std;
 
// This function returns repeating sequence of
// a fraction.  If repeating sequence doesn't
// exits, then returns empty string
string fractionToDecimal(int numr, int denr)
{
    string res; // Initialize result
 
    // Create a map to store already
    // seen remainders remainder is used
    // as key and its position in
    // result is stored as value.
    // Note that we need
    // position for cases like 1/6.
    // In this case,the recurring sequence
    // doesn't start from first
    // remainder.
    map<int, int> mp;
    mp.clear();
 
    // Find first remainder
    int rem = numr % denr;
 
    // Keep finding remainder until either remainder
    // becomes 0 or repeats
    while ((rem != 0)
           && (mp.find(rem) == mp.end()))
    {
        // Store this remainder
        mp[rem] = res.length();
 
        // Multiply remainder with 10
        rem = rem * 10;
 
        // Append rem / denr to result
        int res_part = rem / denr;
        res += to_string(res_part);
 
        // Update remainder
        rem = rem % denr;
    }
 
    return (rem == 0) ? "" : res.substr(mp[rem]);
}
 
// Driver code
int main()
{
    int numr = 50, denr = 22;
    string res = fractionToDecimal(numr, denr);
    if (res == "")
        cout << "No recurring sequence";
    else
        cout << "Recurring sequence is " << res;
    return 0;
}

// Java program to find
// repeating sequence
// in a fraction
import java.util.*;
class GFG {
 
    // This function returns repeating
    // sequence of a fraction. If
    // repeating sequence doesn't
    // exits, then returns empty String
    static String fractionToDecimal(int numr, int denr)
    {
        // Initialize result
        String res = "";
 
        // Create a map to store already
        // seen remainders. Remainder is
        // used as key and its position in
        // result is stored as value.
        // Note that we need position for
        // cases like 1/6.  In this case,
        // the recurring sequence doesn't
        // start from first remainder.
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.clear();
 
        // Find first remainder
        int rem = numr % denr;
 
        // Keep finding remainder until
        //  either remainder becomes 0 or repeats
        while ((rem != 0) && (!mp.containsKey(rem)))
        {
            // Store this remainder
            mp.put(rem, res.length());
 
            // Multiply remainder with 10
            rem = rem * 10;
 
            // Append rem / denr to result
            int res_part = rem / denr;
            res += String.valueOf(res_part);
 
            // Update remainder
            rem = rem % denr;
        }
 
        if (rem == 0)
            return "";
        else if (mp.containsKey(rem))
            return res.substring(mp.get(rem));
 
        return "";
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int numr = 50, denr = 22;
        String res = fractionToDecimal(numr, denr);
        if (res == "")
            System.out.print("No recurring sequence");
        else
            System.out.print("Recurring sequence is "
                             + res);
    }
}
 
// This code is contributed by gauravrajput1

# Python3 program to find repeating
# sequence in a fraction
 
# This function returns repeating sequence
# of a fraction.If repeating sequence doesn't
# exits, then returns empty string
 
 
def fractionToDecimal(numr, denr):
 
    # Initialize result
    res = ""
 
    # Create a map to store already seen
    # remainders. Remainder is used as key
    # and its position in result is stored
    # as value. Note that we need position
    # for cases like 1/6.  In this case,
    # the recurring sequence doesn't start
    # from first remainder.
    mp = {}
 
    # Find first remainder
    rem = numr % denr
 
    # Keep finding remainder until either
    # remainder becomes 0 or repeats
    while ((rem != 0) and (rem not in mp)):
 
        # Store this remainder
        mp[rem] = len(res)
 
        # Multiply remainder with 10
        rem = rem * 10
 
        # Append rem / denr to result
        res_part = rem // denr
        res += str(res_part)
 
        # Update remainder
        rem = rem % denr
 
    if (rem == 0):
        return ""
    else:
        return res[mp[rem]:]
 
 
# Driver code
numr, denr = 50, 22
res = fractionToDecimal(numr, denr)
 
if (res == ""):
    print("No recurring sequence")
else:
    print("Recurring sequence is", res)
 
# This code is contributed by divyeshrabadiya07

// C# program to find repeating sequence
// in a fraction
using System;
using System.Collections.Generic;
 
class GFG {
 
    // This function returns repeating
    // sequence of a fraction. If
    // repeating sequence doesn't
    // exits, then returns empty String
    static string fractionToDecimal(int numr, int denr)
    {
        // Initialize result
        string res = "";
 
        // Create a map to store already
        // seen remainders. Remainder is
        // used as key and its position in
        // result is stored as value.
        // Note that we need position for
        // cases like 1/6.  In this case,
        // the recurring sequence doesn't
        // start from first remainder.
        Dictionary<int, int> mp
            = new Dictionary<int, int>();
 
        // Find first remainder
        int rem = numr % denr;
 
        // Keep finding remainder until
        // either remainder becomes 0
        // or repeats
        while ((rem != 0) && (!mp.ContainsKey(rem)))
        {
 
            // Store this remainder
            mp[rem] = res.Length;
 
            // Multiply remainder with 10
            rem = rem * 10;
 
            // Append rem / denr to result
            int res_part = rem / denr;
            res += res_part.ToString();
 
            // Update remainder
            rem = rem % denr;
        }
 
        if (rem == 0)
            return "";
        else if (mp.ContainsKey(rem))
            return res.Substring(mp[rem]);
 
        return "";
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int numr = 50, denr = 22;
        string res = fractionToDecimal(numr, denr);
 
        if (res == "")
            Console.Write("No recurring sequence");
        else
            Console.Write("Recurring sequence is " + res);
    }
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript program to find
// repeating sequence
// in a fraction
 
    // This function returns repeating
    // sequence of a fraction. If
    // repeating sequence doesn't
    // exits, then returns empty String
    function fractionToDecimal(numr, denr)
    {
        // Initialize result
        let res = "";
  
        // Create a map to store already
        // seen remainders. Remainder is
        // used as key and its position in
        // result is stored as value.
        // Note that we need position for
        // cases like 1/6.  In this case,
        // the recurring sequence doesn't
        // start from first remainder.
        let mp = new Map();
        mp.clear();
  
        // Find first remainder
        let rem = numr % denr;
  
        // Keep finding remainder until
        //  either remainder becomes 0 or repeats
        while ((rem != 0) && (!mp.has(rem)))
        {
            // Store this remainder
            mp.set(rem, res.length);
  
            // Multiply remainder with 10
            rem = rem * 10;
  
            // Append rem / denr to result
            let res_part = Math.floor(rem / denr);
            res += res_part.toString();
  
            // Update remainder
            rem = rem % denr;
        }
  
        if (rem == 0)
            return "";
        else if (mp.has(rem))
            return res.substr(mp.get(rem));
  
        return "";
    }
 
// Driver program
 
      let numr = 50, denr = 22;
      let res = fractionToDecimal(numr, denr);
      if (res == "")
          document.write("No recurring sequence");
      else
          document.write("Recurring sequence is "
                             + res);
       
</script>

Recurring sequence is 27

Este artículo es una contribución de Dhruv Mahajan . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.