# Find Recurring Sequence in a Fraction

Given a fraction, find a recurring sequence of digits if it exists, otherwise, print “No recurring sequence”.

**Examples:**

Become a success story instead of just reading about them. Prepare for coding interviews at Amazon and other top product-based companies with our **Amazon Test Series**. Includes **topic-wise practice questions on all important DSA topics** along with **10 practice contests** of 2 hours each. Designed by industry experts that will surely help you practice and sharpen your programming skills. Wait no more, start your preparation today!

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

## We strongly recommend that you click here and practice it, before moving on to the solution.

**When does the fractional part repeat?**

Let us simulate the process of converting fractions to decimals. Let us look at the part where we have already figured out the integer part, which is floor(numerator/denominator). Now we are left with ( remainder = numerator%denominator ) / denominator.

If you remember the process of converting to decimal, at each step we do the following :

- Multiply the remainder by 10.
- Append the remainder/denominator to the result.
- Remainder = remainder % denominator.

At any moment, if the remainder becomes 0, we are done.

However, when there is a recurring sequence, the remainder never becomes 0. For example, if you look at 1/3, the remainder never becomes 0.

Below is one important observation :

If we start with the remainder ‘rem’ and if the remainder repeats at any point in time, the digits between the two occurrences of ‘rem’ keep repeating.

So the idea is to store seen remainders in a map. Whenever a remainder repeats, we return the sequence before the next occurrence.

Below is the implementation of the above idea.

## C++

`// 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

`// 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

`# 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#

`// 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.ContainsValue(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` |

## Javascript

`<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>` |

**Output : **

Recurring sequence is 27

This article is contributed by **Dhruv Mahajan**. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above