166. Fraction to Recurring Decimal

MediumHash TableMathString
Leetcode Link

Problem Description

The problem requires us to represent a fraction given by two integers as a string. The numerator is the top part of the fraction, while the denominator is the bottom part. The output should be a non-reduced fraction converted into a decimal format string. If the decimal part of the fraction repeats indefinitely, we need to identify this repeating sequence and enclose it within parentheses in our string.

To clarify with an example, if we are given numerator = 1 and denominator = 3, the decimal part of this fraction is 0.333..., which repeats indefinitely. Therefore, the output should be "0.(3)" to indicate that the 3 is a repeating sequence.

Also, it's important to handle the sign of the result correctly. If the fraction is negative (meaning the numerator and denominator have opposite signs), there should be a minus sign before the fraction.

Intuition

The intuition behind the solution can be broken down into a few steps:

  1. Handle Zero: If the numerator is 0, the result is 0, regardless of the denominator.

  2. Determine the Sign: Check the sign of the numerator and denominator. If only one of them is negative, the result should have a minus sign.

  3. Integer Part: Divide the absolute values of the numerator by the denominator to get the integer part of the result. Add the integer part to the result string.

  4. Fractional Part: After getting the integer part, we need to process the fractional part (if there is any). Take the remainder of the division (this would be our new numerator) and proceed to the next step.

  5. Recurring Decimals: To represent the fraction part, we multiply the remainder by 10 and then divide by the denominator to get each decimal digit. We continue this process and keep track of the remainders in a map/dictionary to detect repetition. If the remainder repeats, that means we have found a cycle and thus a recurring decimal. We use this information to place parentheses in the string around the repeating part.

  6. Constructing the Fraction String: We keep appending the results of the division to the answer string. Once the repetition is detected, we insert a '(' at the correct position (using the map/dictionary to find where the cycle started) and add a ')' at the end of the result string.

This solution leverages long division and a mapping strategy to successfully note and handle recurring decimals, constructing the desired string representation for the fraction.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The implementation of the solution can be broken down into the following key algorithmic steps:

  1. Identifying whether the result is negative:

    • This is done by checking if the numerator and the denominator have opposite signs using an exclusive OR operation numerator > 0) ^ (denominator > 0). If the result is negative, a negative sign '-' is added in the beginning.

  2. Extracting integer part:

    • The absolute values of the numerator and denominator are found using abs(), and the integer part of the fraction is obtained by integer division num // d. This part is added to the result string as the initial part before the decimal point.

  3. Handling the fractional part:

    • The remainder num % d after the integer division becomes the new numerator for the fractional part. If the remainder is zero, the function immediately returns the result because there is no fractional part.

  4. Setting up a map to identify repeating fractions:

    • A map (or dictionary in Python), named mp, is set up to remember the position of each remainder in the output string. The position is stored so that when we encounter the same remainder again, we know that the sequence of decimals is starting to repeat.

  5. Performing the long division for the decimal part:

    • Long division is simulated by multiplying the remainder (new numerator) by 10 and again performing integer division by the denominator to find the next digit of the decimal part. This process (num *= 10) continues in a loop until we either reach a remainder of zero or find a repeated remainder.

  6. Detecting repeating sequences:

    • During each iteration of the long division, before appending the next digit to the result, we check if the current remainder is already in the map.
      • If it's not, we add the remainder along with the current length of the result string to the map (mp[num] = len(res)).
      • If it is, we've identified a repeating sequence. We insert a parenthesis at the index where this remainder first appeared (res.insert(idx, '(')), and add the closing parenthesis at the end of the current result (res.append(')')), and then break out of the loop.

  7. Building the final result string:

    • The result is formed by combining all the parts of the fraction into a single string with ''.join(res).

The key data structures used in this solution are:

  • A list (res) to construct the string since strings in Python are immutable, and updating an immutable string repeatedly would be inefficient.
  • A dictionary (mp) to keep track of the remainders and their positions in the result list, which is crucial for identifying repeating decimals.

Here is an illustration of the process with numerator 1 and denominator 6 which should yield the result "0.1(6)":

  • Integer division gives us the integer part 0 and a remainder of 1.
  • We set up our result list with ['0', '.'] and our map as {}.
  • We multiply the numerator by 10, getting 10, and dividing by 6 gives us 1 with a remainder of 4.
  • We append the 1 to our result list (making it ['0', '.', '1']) and store the position of the remainder 4 in the map ({4: 3}).
  • We repeat the multiplication and division to get another digit which is 6 with a remainder of 4 again.
  • Since 4 is already in the map, we insert a ( at the index from the map (making the result list ['0', '.', '1', '(', '6']) and append a ) at the end (finally having ['0', '.', '1', '(', '6', ')']).
  • We join the list and return the string "0.1(6)".

The algorithm is effective at handling both non-repeating and repeating decimals, terminating appropriately once the division is complete or a repetition is found.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let's use a small example to illustrate the solution approach with the numerator 1 and the denominator 7. The expected result is "0.(142857)" since 1/7 results in a repeating decimal with repeating sequence "142857".

Now, we walk through the steps of the solution:

  1. Identifying whether the result is negative:

    • Both 1 and 7 are positive, so the result will also be positive. No negative sign is needed.

  2. Extracting integer part:

    • Integer division of 1 // 7 equals 0, since 1 is less than 7. The result string starts with "0.".

  3. Handling the fractional part:

    • The remainder now is 1 % 7 which is 1, so there is a fractional part. This remainder is the starting point for our long division.

  4. Setting up a map to identify repeating fractions:

    • We create an empty map mp = {} to keep track of our remainders and where they first appear in the result.

  5. Performing the long division for the decimal part:

    • We multiply the remainder by 10, getting 10, and divide by 7 which gives us 1 with a new remainder 3. We append 1 to our result string and add 3 to the map pointing to its current index in the result string, index 2 (right after "0.").

  6. Detecting repeating sequences:

    • We repeat the multiplication and division. With the new remainder 3, we get 30 / 7 which is 4 with remainder 2. We do this process iteratively:
      • 20 / 7 gives 2 and the remainder 6
      • 60 / 7 gives 8 and the remainder 4
      • 40 / 7 gives 5 and the remainder 5
      • 50 / 7 gives 7 and the remainder 1
    • When we reach the remainder 1 again, it's already in our map; it indicates the start of the repeating sequence. Thus, we insert a parenthesis at the index of the first occurrence of 1 in our result list and a closing parenthesis at the end of the list.

  7. Building the final result string:

    • The result string now becomes "0.142857". To represent the repeating sequence, we place parentheses around "142857" to get "0.(142857)".

Throughout every step of this example, the algorithm carefully handles the integer part and fractional part of the fraction, accurately recording each digit of the repeating decimal, and correctly identifies the beginning of the repeating sequence to enclose it within parentheses, resulting in the correct representation of 1/7 as a string with repeating decimal notation.

Solution Implementation

1class Solution:
2    def fraction_to_decimal(self, numerator: int, denominator: int) -> str:
3        # Base case: if the numerator is 0, then the result is "0"
4        if numerator == 0:
5            return '0'
6
7        # Initialize the result as an empty list to store the characters of the answer
8        result = []
9      
10        # Determine if the result is negative, and add '-' if necessary
11        is_negative = (numerator > 0) ^ (denominator > 0)
12        if is_negative:
13            result.append('-')
14
15        # Use absolute values for division
16        numerator_abs = abs(numerator)
17        denominator_abs = abs(denominator)
18
19        # Add the integer part of the quotient to the result
20        result.append(str(numerator_abs // denominator_abs))
21      
22        # Calculate the remainder
23        remainder = numerator_abs % denominator_abs
24      
25        # If there is no remainder, convert the result to a string and return
26        if remainder == 0:
27            return ''.join(result)
28      
29        # Add the decimal point as we have a remainder
30        result.append('.')
31      
32        # Dictionary to store seen remainders and their corresponding indices in the result
33        seen_remainders = {}
34
35        # Repeat until the remainder is 0 or we have seen the remainder before
36        while remainder != 0:
37            # Check if we have seen this remainder before
38            if remainder in seen_remainders:
39                # If so, insert '(' at the index of the first occurrence and ')' at the end
40                idx = seen_remainders[remainder]
41                result.insert(idx, '(')
42                result.append(')')
43                break  # repeating pattern found, break out of the loop
44
45            # If the remainder is not seen before, record its index
46            seen_remainders[remainder] = len(result)
47
48            # Multiply remainder by 10 for the next digit
49            remainder *= 10
50
51            # Add the digit of the quotient to the result
52            result.append(str(remainder // denominator_abs))
53
54            # Update the remainder
55            remainder %= denominator_abs
56
57        # Convert the result list to string and return
58        return ''.join(result)
59
1class Solution {
2    public String fractionToDecimal(int numerator, int denominator) {
3        // Check for zero numerator which means the result is 0
4        if (numerator == 0) {
5            return "0";
6        }
7
8        // StringBuilder to build the final string result
9        StringBuilder resultBuilder = new StringBuilder();
10
11        // Determine the sign of the result (neg if numerator XOR denominator is negative)
12        boolean isNegative = (numerator > 0) ^ (denominator > 0);
13        resultBuilder.append(isNegative ? "-" : "");
14
15        // Convert to long to prevent integer overflow
16        long num = Math.abs((long) numerator);
17        long denom = Math.abs((long) denominator);
18
19        // Append the integer part of the quotient to the result string
20        resultBuilder.append(num / denom);
21        num %= denom;  // Get the remainder
22
23        // If there is no remainder, we can return the result as it's not a fraction
24        if (num == 0) {
25            return resultBuilder.toString();
26        }
27
28        // Fraction part starts after the decimal point
29        resultBuilder.append(".");
30
31        // Map to store already seen remainders and their positions in resultBuilder
32        Map<Long, Integer> remainderPositions = new HashMap<>();
33
34        // Loop until no remainder or repeated remainder is found
35        while (num != 0) {
36            remainderPositions.put(num, resultBuilder.length());
37            num *= 10; // Multiply by 10 to get the numerator for next digit
38            resultBuilder.append(num / denom); // Append the quotient digit
39            num %= denom;  // Get the new remainder
40
41            // Check if this remainder has been seen before
42            if (remainderPositions.containsKey(num)) {
43                // Insert the opening parenthesis at the position of the first occurrence of this remainder
44                int index = remainderPositions.get(num);
45                resultBuilder.insert(index, "(");
46                // Append closing parenthesis at the end of the result string
47                resultBuilder.append(")");
48                break;
49            }
50        }
51        // Convert the StringBuilder to a string and return it
52        return resultBuilder.toString();
53    }
54}
55
1#include <string>
2#include <unordered_map>
3#include <cmath> // For std::abs
4#include <cstdlib> // For llabs (long long abs)
5
6// We use an alias LL for long long to improve readability.
7using LL = long long;
8
9class Solution {
10public:
11    // Converts a fraction given by numerator and denominator to its decimal string representation.
12    // If the decimal representation has a repeating sequence, it encloses it in parentheses.
13    string fractionToDecimal(int numerator, int denominator) {
14        // Handle the case when the fraction is zero.
15        if (numerator == 0) {
16            return "0";
17        }
18
19        // Result string to accumulate the answer.
20        string result;
21
22        // Determine if the result is negative, and if true, prepend a minus sign.
23        bool isNegative = (numerator > 0) ^ (denominator > 0); // XOR evaluates to true if signs are different.
24        if (isNegative) {
25            result += "-";
26        }
27
28        // Convert both parts to positive long longs to avoid overflow and for further processing.
29        LL numeratorLL = std::llabs(static_cast<LL>(numerator));
30        LL denominatorLL = std::llabs(static_cast<LL>(denominator));
31
32        // Add the integer part to the result.
33        result += std::to_string(numeratorLL / denominatorLL);
34
35        // Calculate the remainder and process the fractional part, if any.
36        numeratorLL %= denominatorLL;
37        if (numeratorLL == 0) {
38            // If there is no remainder, return the integer part.
39            return result;
40        }
41      
42        // Since there is a fractional part, append the decimal point.
43        result += ".";
44
45        // Use a map to store numerators and their respective positions in case of repeat.
46        std::unordered_map<LL, int> numeratorsMap;
47
48        while (numeratorLL) {
49            // Store the position of the numerator before the multiplication.
50            numeratorsMap[numeratorLL] = result.size();
51
52            // Update the numerator to get the next digit after the decimal point.
53            numeratorLL *= 10;
54
55            // Add the digit to the result.
56            result += std::to_string(numeratorLL / denominatorLL);
57
58            // Update the remainder.
59            numeratorLL %= denominatorLL;
60
61            // If the numerator repeats, a repeating cycle is found.
62            if (numeratorsMap.count(numeratorLL)) {
63                // Insert the opening parenthesis at the start index of the repeating part.
64                int startIndex = numeratorsMap[numeratorLL];
65                result.insert(startIndex, "(");
66                // Append the closing parenthesis to the result to denote the repeating cycle.
67                result += ")";
68                break;
69            }
70        }
71
72        // Return the decimal representation of the fraction.
73        return result;
74    }
75};
76
1// Converts a number to its absolute value and ensures it is of type bigint.
2function llabs(value: number): bigint {
3    return BigInt(Math.abs(value));
4}
5
6// Converts a fraction given by numerator and denominator to its decimal string representation.
7// If the decimal representation has a repeating sequence, it encloses it in parentheses.
8function fractionToDecimal(numerator: number, denominator: number): string {
9    // Handle the case when the fraction is zero.
10    if (numerator === 0) {
11        return "0";
12    }
13
14    // Result string to accumulate the answer.
15    let result = "";
16
17    // Determine if the result is negative, and if true, prepend a minus sign.
18    let isNegative = (numerator > 0) !== (denominator > 0); // XOR evaluates to true if signs are different.
19    if (isNegative) {
20        result += "-";
21    }
22
23    // Convert both parts to positive BigInts to avoid overflow and for further processing.
24    let numeratorBigInt = llabs(numerator);
25    let denominatorBigInt = llabs(denominator);
26
27    // Add the integer part to the result.
28    result += (numeratorBigInt / denominatorBigInt).toString();
29  
30    // Calculate the remainder and process the fractional part, if any.
31    numeratorBigInt = numeratorBigInt % denominatorBigInt;
32    if (numeratorBigInt == 0n) {
33        // If there is no remainder, return the integer part.
34        return result;
35    }
36
37    // Since there is a fractional part, append the decimal point.
38    result += ".";
39
40    // Use a map to store BigInt numerators and their respective positions in result.
41    let numeratorsMap = new Map<bigint, number>();
42
43    while (numeratorBigInt) {
44        // Store the position of the numerator before the multiplication.
45        numeratorsMap.set(numeratorBigInt, result.length);
46
47        // Update the numerator to get the next digit after the decimal point.
48        numeratorBigInt *= 10n;
49
50        // Add the digit to the result.
51        result += (numeratorBigInt / denominatorBigInt).toString();
52
53        // Update the remainder.
54        numeratorBigInt %= denominatorBigInt;
55
56        // If the numerator repeats, a repeating cycle is found.
57        if (numeratorsMap.has(numeratorBigInt)) {
58            // Insert the opening parenthesis at the start index of the repeating part.
59            let startIndex = numeratorsMap.get(numeratorBigInt);
60            // Append the closing parenthesis to the result to denote the repeating cycle.
61            result = `${result.slice(0, startIndex)}(${result.slice(startIndex)})`;
62            break;
63        }
64    }
65
66    // Return the decimal representation of the fraction.
67    return result;
68}
69
70// Example usage:
71// console.log(fractionToDecimal(1, 2)); // "0.5"
72// console.log(fractionToDecimal(2, 1)); // "2"
73// console.log(fractionToDecimal(2, 3)); // "0.(6)"
74
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the maximum element can be found in:

Time and Space Complexity

Time Complexity

The time complexity of the function fractionToDecimal is primarily dependent on the length of the resulting decimal fraction. In the worst case, this length could be equal to the value of the denominator d, because the longest recurring cycle in a fraction numerator/denominator cannot have more than d - 1 digits.

Within the while loop, multiplication, division, and modulus operations are computed, which are all constant-time operations (O(1)). However, the loop can run up to d times in the worst case, implying a time complexity of O(d).

Therefore, the worst-case time complexity is O(d).

Space Complexity

The space complexity involves the storage used by the res list and the mp dictionary:

  • The res list's size grows linearly with the length of the decimal fraction, which in the worst case can be O(d).
  • The mp dictionary maps previously seen remainders to their corresponding index in res. In the worst case, we might store up to d - 1 distinct remainders, resulting in a space complexity of O(d) for the dictionary.

Thus, the overall space complexity of the function fractionToDecimal is also O(d).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫