Algorithm to Compute the Fraction to Recurring Decimal of the Tw
- 时间:2020-09-12 10:06:27
- 分类:网络文摘
- 阅读:76 次
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)”Hints:
No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
Notice that once the remainder starts repeating, so does the divided result.
Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.
A few test cases help us better design a solution.
1/0 – this should be INF
-1/0 – this should be -INF
24/3 – result is a integer 8 (without .0)
1/2 – result is half 0.5
0/0.5 – result is zero
-2/1 – result is negative -2
1/-2 – result is negative half -0.5
-1/-1 – result is positive 1 (with two negative division)
−2147483648/1 – result is −2147483648 (make sure integer don’t overflow when you do the absolute value)
etc..
The algorithm is just simple math. We compute the remainder, multiple by ten and repeat the same process until the remainder is zero or the remainder appears before – that will be the recurring fraction part/pattern. For example, 1/3=0.33333.
The intelligent part is to put the position of the remainder into the hash map and when the same remainder appears next, we know where to repeat from i.e. the start position.
The return type is string, thus when the denominator is zero, we can totoally return INF or -INF depending on the numerator. Alternatively, we can raise an exception – which seems a good approach as well.
C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | class Solution { public: string fractionToDecimal(int64_t numerator, int64_t denominator) { if (numerator == 0) return "0"; if (denominator == 0) return numerator >= 0 ? "INF" : "-INF"; string r = std::to_string(abs(numerator) / abs(denominator)); if (numerator < 0 ^ denominator < 0) { r = "-" + r; } numerator = abs(numerator); denominator = abs(denominator); int64_t rem = numerator % denominator; if (rem == 0) { return r; } r += "."; unordered_map<int, int> data; while (rem != 0) { if (data.find(rem) != data.end()) { int x = data[rem]; return r.substr(0, x) + "(" + r.substr(x) + ")"; } data[rem] = r.size(); rem *= 10; r += std::to_string(rem / denominator); rem %= denominator; } return r; } }; |
class Solution { public: string fractionToDecimal(int64_t numerator, int64_t denominator) { if (numerator == 0) return "0"; if (denominator == 0) return numerator >= 0 ? "INF" : "-INF"; string r = std::to_string(abs(numerator) / abs(denominator)); if (numerator < 0 ^ denominator < 0) { r = "-" + r; } numerator = abs(numerator); denominator = abs(denominator); int64_t rem = numerator % denominator; if (rem == 0) { return r; } r += "."; unordered_map<int, int> data; while (rem != 0) { if (data.find(rem) != data.end()) { int x = data[rem]; return r.substr(0, x) + "(" + r.substr(x) + ")"; } data[rem] = r.size(); rem *= 10; r += std::to_string(rem / denominator); rem %= denominator; } return r; } };
Java: we use a StringBuilder to build the string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | class Solution { public String fractionToDecimal(int numerator, int denominator) { if (denominator == 0) { return (numerator >= 0) ? "INF" : "-INF"; } if (numerator == 0) return "0"; long a = Math.abs(Long.valueOf(numerator)); long b = Math.abs(Long.valueOf(denominator)); long rem = a % b; StringBuilder sb = new StringBuilder(); if (numerator < 0 ^ denominator < 0) { sb.append('-'); } sb.append(a / b); if (rem == 0) { return sb.toString(); } sb.append('.'); Map<Long, Integer> map = new HashMap<>(); while (rem != 0) { if (map.containsKey(rem)) { sb.insert(map.get(rem), "("); sb.append(")"); break; } map.put(rem, sb.length()); rem *= 10; sb.append(rem / b); rem = rem % b; } return sb.toString(); } } |
class Solution { public String fractionToDecimal(int numerator, int denominator) { if (denominator == 0) { return (numerator >= 0) ? "INF" : "-INF"; } if (numerator == 0) return "0"; long a = Math.abs(Long.valueOf(numerator)); long b = Math.abs(Long.valueOf(denominator)); long rem = a % b; StringBuilder sb = new StringBuilder(); if (numerator < 0 ^ denominator < 0) { sb.append('-'); } sb.append(a / b); if (rem == 0) { return sb.toString(); } sb.append('.'); Map<Long, Integer> map = new HashMap<>(); while (rem != 0) { if (map.containsKey(rem)) { sb.insert(map.get(rem), "("); sb.append(")"); break; } map.put(rem, sb.length()); rem *= 10; sb.append(rem / b); rem = rem % b; } return sb.toString(); } }
The complexity (both time and space) is O(b) if we want to compute the a/b. That is because it has at most b different remainders and the algorithm will terminate after b iterations at least.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:数学题:小雨家有6个从里面量得底面积是302 数学题:截至2011年年末 被油漆过的小正方体有多少个?(六上) 戴口罩出门买口罩数学题 加一笔,让等式成立 找规律8+11=? 三个全程的问题解析 两个质数的和差积商一定都还是质数吗? 谁是单位“1”?(六上数学题) 有梦就有机会
- 评论列表
-
- 添加评论