## Saturday, March 5, 2016

### Find Recurring Sequence in a Fraction - GeeksforGeeks

Find Recurring Sequence in a Fraction - GeeksforGeeks
Related: leetcode 166: Fraction to Recurring Decimal

Given a fraction, find recurring sequence of digits if exists, otherwise print "No recurring sequence".
```Input : Numerator = 50, Denominator = 22
Output : Recurring sequence is 27
Explanation : 50/22 = 2.272727272..... ```
If we start with remainder ‘rem’ and if the remainder repeats at any point of time, the digits between the two occurrence 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.
`string fractionToDecimal(``int` `numr, ``int` `denr)`
`{`
`    ``string res; ``// Initialize result`
`    ``// Create a map to store already seen remainders`
`    ``map <``int``, ``bool``> 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] = 1;`
`        ``// 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;`
`}`