NUHMAN.com

Introduction

LeetCode 166 asks us to convert a fraction into its decimal form, ensuring that if the decimal is repeating (recurring), we represent the repeating part correctly. If the fraction is finite, we return the decimal form without any parentheses. If the decimal is repeating, we enclose the repeating part in parentheses.

Problem Statement

Given two integers, numerator and denominator, representing a fraction, return the decimal representation of the fraction. If the decimal is repeating, enclose the repeating part in parentheses.

Function Signature:

go

func fractionToDecimal(numerator int, denominator int) string

• Input:
• numerator: An integer representing the numerator of the fraction.
• denominator: An integer representing the denominator of the fraction.
• Output:
• A string representing the decimal form of the fraction, where the repeating part is enclosed in parentheses, if applicable.

Approach

The problem can be approached by simulating the long division process. Here’s a step-by-step breakdown of the approach:

Steps:

1. Handle Edge Case for Zero:

• If the numerator is 0, the result is simply "0".

1. Handle Signs:

• We need to account for the signs of the numerator and denominator. If the result is negative, the negative sign should only appear once.

1. Handle Integer Part:

• Perform integer division to calculate the integer part of the fraction.

1. Handle Fractional Part:

• Use long division to calculate the fractional part. Keep track of remainders. If a remainder repeats, it means the fraction has a repeating decimal.

1. Handle Repeating Decimals:

• To identify when the decimal repeats, we can use a hashmap (or dictionary) to store the positions of the remainders. When a remainder repeats, it indicates that the decimal will start repeating from the current position.

1. Return Result:

• If a repeating decimal is detected, place parentheses around the repeating part and return the result.

Time Complexity:

• O(n), where n is the number of digits in the fractional part before the repetition starts. This is because the division process is based on the remainders, and there can be at most n unique remainders before they start repeating.

Space Complexity:

• O(n) for storing the remainders in the hashmap to detect repetitions.

Go Implementation

go

import "strconv"

func fractionToDecimal(numerator int, denominator int) string {
    // If numerator is 0, return "0"
    if numerator == 0 {
        return "0"
    }
    
    // Determine the sign of the result
    result := ""
    if (numerator < 0) != (denominator < 0) {
        result = "-"
    }
    
    // Work with absolute values of numerator and denominator
    numerator = abs(numerator)
    denominator = abs(denominator)
    
    // Integer part of the result
    integerPart := numerator / denominator
    result += strconv.Itoa(integerPart)
    
    // If there is no remainder, return the result
    remainder := numerator % denominator
    if remainder == 0 {
        return result
    }
    
    // Add decimal point
    result += "."
    
    // HashMap to store the remainder and its position in the decimal part
    remainderMap := make(map[int]int)
    
    // Start calculating the fractional part
    decimalPart := ""
    index := 0
    for remainder != 0 {
        // If the remainder has been seen before, it's repeating
        if pos, found := remainderMap[remainder]; found {
            decimalPart = decimalPart[:pos] + "(" + decimalPart[pos:] + ")"
            return result + decimalPart
        }
        
        // Store the position of the remainder
        remainderMap[remainder] = index
        
        // Long division: Multiply remainder by 10 and divide again
        remainder *= 10
        decimalPart += strconv.Itoa(remainder / denominator)
        remainder = remainder % denominator
        
        index++
    }
    
    return result + decimalPart
}

// Helper function to get the absolute value
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Explanation of the Code:

1. Handle Zero Case:

• If the numerator is 0, return "0" because any fraction with a 0 numerator is 0.

2. Handle Signs:

• We check the signs of the numerator and denominator. If one of them is negative, the result should be negative. We store this negative sign in the result variable.

3. Integer Part:

• The integer part is obtained by performing integer division (numerator / denominator), and we append this to the result string.

4. Fractional Part Calculation:

• If the remainder is 0 (i.e., no fractional part), we return the result immediately.
• Otherwise, we append a decimal point (".") to the result and begin calculating the fractional part.

5. Detect Repeating Decimals:

• We use a hashmap (remainderMap) to store the remainder and its corresponding index in the fractional part. This allows us to detect when a remainder repeats, indicating the start of a recurring decimal.
• If the remainder repeats, we insert parentheses around the repeating part of the decimal.

6. Helper Function abs:

• The helper function abs is used to get the absolute value of the numerator and denominator since we are working with their absolute values to simplify the division.

Example

Example 1:

go

numerator := 1
denominator := 2
result := fractionToDecimal(numerator, denominator)
fmt.Println(result) // Output: "0.5"

Explanation:

• The fraction 1/2 results in 0.5, which is not a repeating decimal, so the output is "0.5".

Example 2:

go

numerator := 2
denominator := 1
result := fractionToDecimal(numerator, denominator)
fmt.Println(result) // Output: "2"

Explanation:

• The fraction 2/1 is an integer, so the output is simply "2".

Example 3:

go

numerator := 4
denominator := 333
result := fractionToDecimal(numerator, denominator)
fmt.Println(result) // Output: "0.(012)"

Explanation:

• The fraction 4/333 results in the repeating decimal 0.012012..., so the output is "0.(012)", indicating the repeating part is "012".

Example 4:

go

numerator := 1
denominator := 6
result := fractionToDecimal(numerator, denominator)
fmt.Println(result) // Output: "0.1(6)"

Explanation:

• The fraction 1/6 results in the repeating decimal 0.166666..., so the output is "0.1(6)", indicating that 6 is repeating.

Conclusion

LeetCode 166 is a problem that requires us to convert a fraction into its decimal representation, identifying and formatting repeating decimals. The solution uses long division and a hashmap to track remainders and detect repeating decimals. This approach is efficient and handles both finite and repeating decimals correctly.