Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/166.html

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 104 for all the given inputs.

 

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)"

 

Constraints:

  • -231 <= numerator, denominator <= 231 - 1
  • denominator != 0

Algorithm

Int needs to be converted to long type before taking the absolute value.

To find the cycle is to get another number, see if this number appears before. In order to save search time, we use a hash table to store the number in each decimal position.

There is also a little trick, because you have to calculate each decimal position, the method adopted is to multiply the remainder by 10 each time, and then divide by the divisor, the quotient obtained is the next digit of the decimal. When the newly calculated number has appeared before in map, add a left parenthesis at the beginning of the loop and a right parenthesis at the end.

Code

  • import java.util.HashMap;
    
    public class Fraction_to_Recurring_Decimal {
    
         // test: 5 / 6 = 0.833333 = 0.8(3)
    
        public static void main(String[] args) {
            Fraction_to_Recurring_Decimal out = new Fraction_to_Recurring_Decimal();
            Solution s = out.new Solution();
    
            System.out.println(s.fractionToDecimal(-1, -2147483648));
        }
    
        class Solution {
    
            public String fractionToDecimal(int numeratorOriginal, int denominatorOriginal) {
    
                // @note: sign
                long n1 = numeratorOriginal > 0 ? 1 : -1;
                long n2 = denominatorOriginal > 0 ? 1 : -1;
                String sign = n1 * n2 > 0 ? "" : "-";
    
                // @note: missed below, after getting sign, convert to all positives
                /*
    
                    @note: below will error if directly get abs
                            for int, abs(-2147483648) = -2147483648
    
                    numerator = Math.abs(numerator); // possible overflow
                    denominator = Math.abs(denominator); // possible overflow
    
                */
    
                long numerator = Math.abs((long)numeratorOriginal); // possible overflow
                long denominator = Math.abs((long)denominatorOriginal); // possible overflow
    
                if (denominator == 0) {
                    return "";
                } else if (numerator == 0) {
                    return "0";
                } else if (numerator % denominator == 0) {
                    return sign + String.valueOf(numerator / denominator);
                }
    
                StringBuilder result = new StringBuilder();
                result.append(sign);
    
                // hashmap to save if a repeated result, meaning recurring
                HashMap<Long, Integer> hm = new HashMap<>();
    
                // digit before .
                result.append(String.valueOf(numerator / denominator));
    
                result.append(".");
    
                // digit after .
                long end = 10 * (numerator % denominator);
                int i = 1;
    
                // test: 1 / 4 = 0.25
                while (end != 0) { // @note: stop condition
                    if (hm.containsKey(end)) {
                        // recurring
                        int pos = hm.get(end);
                        result.insert(result.indexOf(".") + pos, "(");
                        result.append(")");
    
                        return result.toString(); // break and return
                    }
    
                    hm.put(end, i);
                    result.append(end / denominator);
    
                    System.out.println(result.toString());
    
                    i++;
                    end = 10 * (end % denominator);
                }
    
                return result.toString();
            }
        }
    }
    
    ############
    
    class Solution {
        public String fractionToDecimal(int numerator, int denominator) {
            if (numerator == 0) {
                return "0";
            }
            StringBuilder sb = new StringBuilder();
            boolean neg = (numerator > 0) ^ (denominator > 0);
            sb.append(neg ? "-" : "");
            long num = Math.abs((long) numerator);
            long d = Math.abs((long) denominator);
            sb.append(num / d);
            num %= d;
            if (num == 0) {
                return sb.toString();
            }
            sb.append(".");
            Map<Long, Integer> mp = new HashMap<>();
            while (num != 0) {
                mp.put(num, sb.length());
                num *= 10;
                sb.append(num / d);
                num %= d;
                if (mp.containsKey(num)) {
                    int idx = mp.get(num);
                    sb.insert(idx, "(");
                    sb.append(")");
                    break;
                }
            }
            return sb.toString();
        }
    }
    
  • class Solution:
        def fractionToDecimal(self, numerator: int, denominator: int) -> str:
            if numerator == 0:
                return '0'
            res = []
            neg = (numerator > 0) ^ (denominator > 0)
            if neg:
                res.append('-')
            num, d = abs(numerator), abs(denominator)
            res.append(str(num // d))
            num %= d
            if num == 0:
                return ''.join(res)
            res.append('.')
            mp = {}
            while num != 0:
                mp[num] = len(res)
                num *= 10
                res.append(str(num // d))
                num %= d
                if num in mp:
                    idx = mp[num]
                    res.insert(idx, '(')
                    res.append(')')
                    break
            return ''.join(res)
    
    ############
    
    class Solution(object):
      def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        ans = "-" if numerator * denominator < 0 else ""
        numerator = abs(numerator)
        denominator = abs(denominator)
        ans += str(numerator / denominator)
        if numerator % denominator:
          ans += "."
        numerator = (numerator % denominator) * 10
        if numerator == 0:
          return ans
        d = {}
        res = []
        while True:
          r = numerator % denominator
          v = numerator / denominator
          if numerator in d:
            idx = d[numerator]
            return ans + "".join(res[:idx]) + "(" + "".join(res[idx:]) + ")"
          res.append(str(v))
          if v == 0:
            d[numerator] = len(res) - 1
            numerator *= 10
            continue
          d[numerator] = len(res) - 1
          numerator = r * 10
          if r == 0:
            return ans + "".join(res)
        return ans + "".join(res)
    
    
  • using LL = long long;
    
    class Solution {
    public:
        string fractionToDecimal(int numerator, int denominator) {
            if (numerator == 0) return "0";
            string res = "";
            bool neg = (numerator > 0) ^ (denominator > 0);
            if (neg) res += "-";
            LL num = abs(numerator);
            LL d = abs(denominator);
            res += to_string(num / d);
            num %= d;
            if (num == 0) return res;
            res += ".";
            unordered_map<LL, int> mp;
            while (num) {
                mp[num] = res.size();
                num *= 10;
                res += to_string(num / d);
                num %= d;
                if (mp.count(num)) {
                    int idx = mp[num];
                    res.insert(idx, "(");
                    res += ")";
                    break;
                }
            }
            return res;
        }
    };
    
  • func fractionToDecimal(numerator int, denominator int) string {
    	if numerator == 0 {
    		return "0"
    	}
    	res := []byte{}
    	neg := numerator*denominator < 0
    	if neg {
    		res = append(res, '-')
    	}
    	num := abs(numerator)
    	d := abs(denominator)
    	res = append(res, strconv.Itoa(num/d)...)
    	num %= d
    	if num == 0 {
    		return string(res)
    	}
    	mp := make(map[int]int)
    	res = append(res, '.')
    	for num != 0 {
    		mp[num] = len(res)
    		num *= 10
    		res = append(res, strconv.Itoa(num/d)...)
    		num %= d
    		if mp[num] > 0 {
    			idx := mp[num]
    			res = append(res[:idx], append([]byte{'('}, res[idx:]...)...)
    			res = append(res, ')')
    			break
    		}
    	}
    
    	return string(res)
    }
    
    func abs(x int) int {
    	if x < 0 {
    		return -x
    	}
    	return x
    }
    
  • // https://leetcode.com/problems/fraction-to-recurring-decimal/
    
    using System.Collections.Generic;
    using System.Text;
    
    public partial class Solution
    {
        public string FractionToDecimal(int numerator, int denominator)
        {
            var n = (long)numerator;
            var d = (long)denominator;
            var sb = new StringBuilder();
            if (n < 0)
            {
                n = -n;
                if (d < 0)
                {
                    d = -d;
                }
                else
                {
                    sb.Append('-');
                }
            }
            else if (n > 0 && d < 0)
            {
                d = -d;
                sb.Append('-');
            }
    
            sb.Append(n / d);
            n = n % d;
            if (n != 0)
            {
                sb.Append('.');
                var dict = new Dictionary<long, int>();
                while (n != 0)
                {
                    int index;
                    if (dict.TryGetValue(n, out index))
                    {
                        sb.Insert(index, '(');
                        sb.Append(')');
                        break;
                    }
                    else
                    {
                        dict.Add(n, sb.Length);
                        n *= 10;
                        sb.Append(n / d);
                        n %= d;
                    }
                }
            }
            return sb.ToString();
        }
    }
    

All Problems

All Solutions