Skip to main content

166. Fraction to Recurring Decimal

medium

Convert a fraction (numerator / denominator) into a decimal string, wrapping any repeating part in parentheses. Classic long-division simulation with a hash map to spot the cycle.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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. 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.

Constraints

  • -2^31 <= numerator, denominator <= 2^31 - 1
  • denominator != 0

Examples

Example 1

Input
numerator = 1, denominator = 2
Output
"0.5"

Example 2

Input
numerator = 2, denominator = 1
Output
"2"

Example 3

Input
numerator = 4, denominator = 333
Output
"0.(012)"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Handle sign separately; work on |numerator| and |denominator|. Cast to a wide enough type — |INT_MIN| overflows 32-bit.

Hint 2

Integer part: q = num / denom. If num % denom == 0, return q (with sign).

Hint 3

Fractional part: simulate long division. Maintain remainder; repeatedly multiply remainder by 10 then divide by denominator to get the next decimal digit.

Hint 4

Detect a repeating cycle by mapping each remainder seen to the index where it appeared. When you revisit a remainder, the digits between the previous occurrence and now repeat — wrap them in parentheses.

Solution approach

Reveal approach

Step 1: handle sign by XOR of input signs; record it and work with absolute values cast to 64-bit (|INT_MIN| overflows int32). Step 2: integer part = num / denom; remainder = num % denom. If remainder is 0, return (sign +) integer_part. Step 3: append '.' to the result. Step 4: simulate long division. Maintain a hash map from remainder to the position in the result where it appeared. Loop while remainder != 0: if remainder is already in the map, insert '(' at that position and append ')' to the end — done; otherwise record map[remainder] = current_result_length, then remainder *= 10, append remainder / denom as a digit, and remainder %= denom. Return result. O(denom) time worst case (number of distinct remainders), O(denom) space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • math
  • hash-map
  • simulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Fraction to Recurring Decimal and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →