Fraction to Recurring Decimal - Practice Coding Problems

Fraction to Recurring Decimal - Problem

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses. For example, 1/3 = 0.(3) where 3 repeats infinitely.

If multiple answers are possible, return any of them. It is guaranteed that the length of the answer string is less than 10^4 for all the given inputs.

Note: If the fraction can be represented as a finite length string, you must return it without parentheses.

Input & Output

Example 1 — Simple Repeating Decimal

$ Input: numerator = 1, denominator = 3

› Output: "0.(3)"

💡 Note: 1 ÷ 3 = 0.333... The digit 3 repeats infinitely, so we enclose it in parentheses: 0.(3)

Example 2 — Finite Decimal

$ Input: numerator = 1, denominator = 2

› Output: "0.5"

💡 Note: 1 ÷ 2 = 0.5 exactly. Since it terminates, no parentheses are needed.

Example 3 — Negative with Repetition

$ Input: numerator = -1, denominator = 6

› Output: "-0.1(6)"

💡 Note: -1 ÷ 6 = -0.1666... The digit 6 repeats after the initial 1, so result is -0.1(6)

Constraints

-2³¹ ≤ numerator, denominator ≤ 2³¹ - 1
denominator ≠ 0

Visualization

Tap to expand

Understanding the Visualization

Input

numerator = 1, denominator = 3

Long Division

Perform division while tracking remainders

Output

"0.(3)" with parentheses around repeating part

Key Takeaway

🎯 Key Insight: When a remainder repeats during long division, the decimal pattern will repeat from that point forward

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is that when performing long division, if a remainder repeats, the decimal digits will repeat from that point forward. The optimal approach uses a hash map to detect remainder repetition in O(1) time. Time: O(d), Space: O(d) where d is the number of decimal digits.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(d)	O(d)	Use hash map to instantly detect remainder repetition
Brute Force Long Division	O(d)	O(d)	Simulate long division and store all remainders to detect repetition

Hash Map Optimization — Algorithm Steps

Handle sign and calculate integer part
Use hash map to track remainder → position mapping
On remainder repeat, insert parentheses at stored position
Continue until remainder becomes 0 or repeats

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Position

Store remainder → position mapping

Instant Lookup

Hash map finds repetition immediately

Insert Parentheses

Use stored position to place opening parenthesis

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    long long remainder;
    int position;
} RemainderEntry;

char* solution(int numerator, int denominator) {
    char* result = (char*)malloc(10000 * sizeof(char));
    int pos = 0;
    
    if (numerator == 0) {
        strcpy(result, "0");
        return result;
    }
    
    // Handle sign
    if ((numerator < 0) ^ (denominator < 0)) {
        result[pos++] = '-';
    }
    
    long long num = abs((long long)numerator);
    long long den = abs((long long)denominator);
    
    // Integer part
    pos += sprintf(result + pos, "%lld", num / den);
    num %= den;
    
    if (num == 0) {
        return result;
    }
    
    // Fractional part
    result[pos++] = '.';
    RemainderEntry remainderMap[10000];
    int mapSize = 0;
    
    while (num != 0) {
        int foundPos = -1;
        for (int i = 0; i < mapSize; i++) {
            if (remainderMap[i].remainder == num) {
                foundPos = remainderMap[i].position;
                break;
            }
        }
        
        if (foundPos != -1) {
            memmove(result + foundPos + 1, result + foundPos, pos - foundPos);
            result[foundPos] = '(';
            pos++;
            result[pos++] = ')';
            break;
        }
        
        remainderMap[mapSize].remainder = num;
        remainderMap[mapSize].position = pos;
        mapSize++;
        
        num *= 10;
        pos += sprintf(result + pos, "%lld", num / den);
        num %= den;
    }
    
    result[pos] = '\0';
    return result;
}

int main() {
    int numerator, denominator;
    scanf("%d", &numerator);
    scanf("%d", &denominator);
    char* result = solution(numerator, denominator);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(d)

Where d is the number of decimal digits before repetition

✓ Linear Growth

Space Complexity

O(d)

Hash map stores up to d remainder-position pairs

✓ Linear Space

89.4K Views

Medium Frequency

~35 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler