166. Fraction to Recurring Decimal - Detailed Explanation

Problem Statement

Description:
Given two integers, numerator and denominator, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses.

Examples:

• Example 1:

  • Input: numerator = 1, denominator = 2
  • Output: "0.5"
  • Explanation: 1/2 equals 0.5, which is finite.

• Example 2:

  • Input: numerator = 2, denominator = 1
  • Output: "2"
  • Explanation: 2/1 equals 2. No fractional part.

• Example 3:

  • Input: numerator = 2, denominator = 3
  • Output: "0.(6)"
  • Explanation: 2/3 equals 0.6666…; the repeating part is "6", so it is enclosed in parentheses.

Constraints:

• The numerator and denominator are both 32-bit signed integers.
• The denominator is not zero.
• The answer should handle negative numbers appropriately.
• If the result is a finite decimal, simply output that number; if it’s recurring, mark the repeating portion in parentheses.

Hints Before Diving Into the Solution

• Hint 1:
  Think about how you perform long division manually. When you divide two numbers, you get a quotient and a remainder. The repeating cycle is detected when a remainder repeats during the division process.

• Hint 2:
  Use a hash map (or dictionary) to store the remainders and their corresponding positions in the result string. When a remainder repeats, it means the digits between the first occurrence and the current index form a repeating cycle.

Approaches to Solve the Problem

Brute Force Approach

Idea:
Simulate the division process until you reach a remainder of 0 (resulting in a terminating decimal) or until you detect a repeating remainder.

Steps:

• Handle the sign of the result.
• Compute the integral part using integer division.
• For the fractional part, repeatedly multiply the remainder by 10 and extract digits.
• Track each remainder along with its position in the result.
• If a remainder repeats, insert parentheses to indicate the recurring part.

Limitations:

• Although this method is straightforward, without the proper tracking (i.e., using a hash map), it can be inefficient or even get stuck in an infinite loop.

Optimal Approach Using Remainder Hash Map

Idea:
Simulate long division using a hash map to record the index at which each remainder occurs. As soon as a remainder repeats, you know the recurring cycle.

Detailed Steps:

1. Sign Handling:
   Check if the result is negative by examining the signs of the numerator and denominator. Convert both to positive for ease of calculation.

2. Compute Integral Part:
   Use integer division to get the integral part and compute the initial remainder.

3. Process the Fractional Part:

   • Initialize an empty hash map (or dictionary) to record each remainder and its corresponding position in the result string.
   • Multiply the remainder by 10 and obtain the next digit by performing division.
   • Record the new remainder.
   • If a remainder is seen again, identify the substring that represents the repeating cycle and insert parentheses.

4. Construct the Result String:
   Combine the integral part and the processed fractional part. If there is no fractional part, simply return the integral part as a string.

Benefits:

• This approach efficiently handles recurring decimals without running indefinitely.
• The use of the hash map makes it easy to identify the start of the repeating sequence.

Step-by-Step Walkthrough with a Visual Example

Let’s walk through the example of numerator = 4 and denominator = 333.

1. Determine the Sign:
   Both numbers are positive, so the result will be positive.

2. Compute the Integral Part:

   • 4 divided by 333 is 0 (integral part)
   • Remainder: 4

3. Processing the Fractional Part:

   • Iteration 1:
     • Multiply remainder (4) by 10 → 40
     • 40 / 333 = 0, remainder becomes 40
     • Record remainder 40 with position 0.
   • Iteration 2:
     • Multiply remainder (40) by 10 → 400
     • 400 / 333 = 1, remainder becomes 400 - (333 * 1) = 67
     • Record remainder 67 with position 1.
   • Iteration 3:
     • Multiply remainder (67) by 10 → 670
     • 670 / 333 = 2, remainder becomes 670 - (333 * 2) = 4
     • Now remainder 4 is encountered again.

4. Detect the Recurrence:
   The remainder 4 was first seen before the fractional part started. The digits produced since then form the repeating cycle. In this case, the cycle is "012" (from the sequence of divisions).

5. Final Result:
   Combine the integral part "0", add the decimal point, and insert the recurring cycle in parentheses: "0.(012)".

Python Code Implementation