Massive Algorithms: Find Recurring Sequence in a Fraction

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;

}

Labels