166: Fraction-to-Recurring-Decimal
Medium

code
- complexity
- time taken

This question is epic.

For this algorithm, I decided to split the division into two sections:

calculating the whole number
- this part is simple as it just requires you to make a floor divison of the numerator and denominator
- we will end up forming a string called wholeNumber to track the string on this side
calculate the decimal
- this part is difficult as you have to account for for repeating parts
- we will end up forming a string called decimal to track the string on this side

First off, we can early return "0" if our numerator == 0:

if (numerator == 0) {
    return "0";
}

Then, we can account for the case where only one of the values out of numerator and denominator contain a negative value. If that is the case, we can add "-" to the front of our answer, and make sure both the numerator and denominator are positive:

string wholeNumber = "";
if (numerator < 0 ^ denominator < 0) {
    wholeNumber += "-";
}
numerator = abs(numerator);
denominator = abs(denominator);

Note, we changed both numerator and denominator to long long instead of int. This is because both values had a range of -2^{31} <= numerator, denominator <= 2^{31} - 1, meaning abs(-2^{31}) = 2^{31} would cause an integer overflow.

The whole number section is really simple; just calculate the quotient value and add it to wholeNumber:

long long quotient = numerator / denominator;
long long remainder = numerator % denominator;
wholeNumber += to_string(quotient);

Then, if remainder == 0, we can early return wholeNumber.

if (remainder == 0) {
    return wholeNumber;
}

Therefore, if we do not early return, it implies there exists a decimal section to the quotient. To calculate each value in the tenths, hundredths, thousandths etc. column, we can simply iterate through these calculations repeatedly:

numerator = remainder * 10;
quotient = numerator / denominator;
remainder = numerator % denominator;
// use quotient to fill in the corresponding decimal column
// repeat these steps again, until numerator = 0;

We can run through an example with 1/7:

// step 1
numerator = 1, quotient = 1/7 = 0, remainder = 1%7 = 1
hence, ans = 0;

// step 2
numerator = 10, quotient = 10/7 = 1, remainder = 10%7 = 3
hence, ans = 0.1;

// step 3
numerator = 30, quotient = 30/7 = 4, remainder = 30%7 = 2
hence, ans = 0.14;

// step 4
numerator = 20, quotient = 20/7 = 2, remainder = 20%7 = 6
hence, ans = 0.142;

// etc.

// step 8
numerator = 10, quotient = 10/7 = 1, remainder = 10%7 = 3
hence, ans = 0.1428571

Notice, after step 8 we get a duplicate numerator value. This allows us to find repeating parts inside the decimal part, as we can encapsulate all the numbers found between step 2 and step 7 inclusive inside brackets. All together, the code looks something like:

unordered_map<long long, int> remainderIndex;

numerator = remainder * 10;
quotient = numerator / denominator;
remainder = numerator % denominator;

string decimal = "";
while (numerator != 0 && !remainderIndex.count(numerator)) {
    remainderIndex[numerator] = decimal.size();
    decimal += to_string(quotient);

    numerator = remainder * 10;
    quotient = numerator / denominator;
    remainder = numerator % denominator;
}

From above, you can see that there are two possible ways to break from the while loop:

when numerator == 0
- this means that we have cleanly divided the numerator with the denominator
- we can simply return wholeNumber + "." + decimal
when remainderIndex.count(numerator)
- this means there exists a repeated part in the decimal
- we keep track of the index, using remainderIndex,where a numerator first appears, allowing us to wrap target sections in brackets

if (remainder == 0) {
    return wholeNumber + "." + decimal;
} else {
    return wholeNumber + "." 
    + decimal.substr(0, remainderIndex[numerator]) 
    + "(" + decimal.substr(remainderIndex[numerator]) + ")";
}

code

class Solution {
public:
    string fractionToDecimal(long long numerator, long long denominator) {
        if (numerator == 0) {
            return "0";
        }

        string wholeNumber = "";
        if (numerator < 0 ^ denominator < 0) {
            wholeNumber += "-";
        }
        numerator = abs(numerator);
        denominator = abs(denominator);

        long long quotient = numerator / denominator;
        long long remainder = numerator % denominator;
        if (quotient > 0) {
            wholeNumber += to_string(quotient);
        } else {
            wholeNumber += "0";
        }

        if (remainder == 0) {
            return wholeNumber;
        }

        unordered_map<long long, int> remainderIndex;

        numerator = remainder * 10;
        quotient = numerator / denominator;
        remainder = numerator % denominator;

        string decimal = "";
        while (numerator != 0 && !remainderIndex.count(numerator)) {
            remainderIndex[numerator] = decimal.size();
            decimal += to_string(quotient);

            numerator = remainder * 10;
            quotient = numerator / denominator;
            remainder = numerator % denominator;
        }

        if (remainder == 0) {
            return wholeNumber + "." + decimal;
        } else {
            return wholeNumber + "." + decimal.substr(0, remainderIndex[numerator]) + "(" + decimal.substr(remainderIndex[numerator]) + ")";
        }
    }
};

166: Fraction-to-Recurring-Decimal Medium

table of contents

code

complexity

time taken

166: Fraction-to-Recurring-Decimal
Medium