166. Fraction to Recurring Decimal
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:
-
Handle Zero: If the numerator is
0
, the result is0
, regardless of the denominator. -
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.
-
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.
-
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.
-
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.
-
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.
Solution Approach
The implementation of the solution can be broken down into the following key algorithmic steps:
-
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.
- This is done by checking if the numerator and the denominator have opposite signs using an exclusive OR operation
-
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 divisionnum // d
. This part is added to the result string as the initial part before the decimal point.
- The absolute values of the numerator and denominator are found using
-
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.
- The remainder
-
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.
- A map (or dictionary in Python), named
-
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.
- 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 (
-
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.
- If it's not, we add the remainder along with the current length of the result string to the map (
- 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.
-
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 result is formed by combining all the parts of the fraction into a single string with
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 of1
. - We set up our result list with ['0', '.'] and our map as
{}
. - We multiply the numerator by 10, getting
10
, and dividing by6
gives us1
with a remainder of4
. - We append the
1
to our result list (making it ['0', '.', '1']) and store the position of the remainder4
in the map ({4: 3}
). - We repeat the multiplication and division to get another digit which is
6
with a remainder of4
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Identifying whether the result is negative:
- Both
1
and7
are positive, so the result will also be positive. No negative sign is needed.
- Both
-
Extracting integer part:
- Integer division of
1 // 7
equals0
, since1
is less than7
. The result string starts with"0."
.
- Integer division of
-
Handling the fractional part:
- The remainder now is
1 % 7
which is1
, so there is a fractional part. This remainder is the starting point for our long division.
- The remainder now is
-
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.
- We create an empty map
-
Performing the long division for the decimal part:
- We multiply the remainder by 10, getting
10
, and divide by7
which gives us1
with a new remainder3
. We append1
to our result string and add3
to the map pointing to its current index in the result string, index2
(right after "0.").
- We multiply the remainder by 10, getting
-
Detecting repeating sequences:
- We repeat the multiplication and division. With the new remainder
3
, we get30 / 7
which is4
with remainder2
. We do this process iteratively:20 / 7
gives2
and the remainder6
60 / 7
gives8
and the remainder4
40 / 7
gives5
and the remainder5
50 / 7
gives7
and the remainder1
- 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 of1
in our result list and a closing parenthesis at the end of the list.
- We repeat the multiplication and division. With the new remainder
-
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)"
.
- The result string now becomes
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
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 beO(d)
. - The
mp
dictionary maps previously seen remainders to their corresponding index inres
. In the worst case, we might store up tod - 1
distinct remainders, resulting in a space complexity ofO(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.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.