166. Fraction to Recurring Decimal (Medium)

https://leetcode.com/problems/fraction-to-recurring-decimal/

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.

Example 1:

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

Example 2:

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

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

Solutions

class Solution {

    // This problem is not easy to get over, you need to pay close attention to the special cases.

    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) {
            return "";
        }

        if (numerator == 0) {
            return "0";
        }

        int sign = 1;
        if (numerator * 1.0 * denominator < 0) {
            sign = -1;
        }

        // following statement is not correct.
        // long num = Math.abs(numerator);
        // long denom = Math.abs(denominator);

        long num = Math.abs(numerator * 1l);
        long denom = Math.abs(denominator * 1l);

        // first get the integer
        long itg = num / denom;
        String ans = itg + "";

        // if it is not exactly divisible. append dot
        long remainder = num % denom;
        if (remainder != 0) {
            ans += ".";
        }

        // length of answer string
        int count = ans.length();

        // keep track of occurred remainders
        Map<Long, Integer> map = new HashMap<>();

        // 2 / 3, remainder is 2, remainder * 10 = 20
        // second get the fraction
        while (remainder != 0) {
            remainder *= 10;

            // fractional part is repeating
            if (map.containsKey(remainder)) {
                int idx = map.get(remainder);

                ans = ans.substring(0, idx) + '(' + ans.substring(idx, count) + ')';

                break;
            }

            map.put(remainder, count);

            long frac = remainder / denom;
            ans += frac;

            remainder = remainder % denom;

            count++;
        }

        if (sign < 0) {
            ans = "-" + ans;
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""