LeetCode Entry
166. Fraction to Recurring Decimal
Calc a/b to string x.y(z)
166. Fraction to Recurring Decimal medium blog post substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1122
Problem TLDR
Calc a/b to string x.y(z) #medium #math
Intuition
Gave up to implement this correctly.
// how to know it is repeating?
// let's just brute-force 10^4 digits
// ok, how to find repeats? kmp (i forgot it)?
// just store visited "(a/b)"
// ok 43 minute, looks for hints, any simpler ideas? (no)
// decide to give up, no time for debugging this
The ideas:
- to divide 1/3 multiply 1*10, and repeat the problem for 1%3 / 3
- to find the repeating part remember the problem “1/3” or just “1”
- to find where the repeating part start, remember the positions for each key “1”
- solve the part before “.” before going next
Approach
- abs(Int.MIN_VALUE) == Int.MIN_VALUE, convert to longs before
abs
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
// 2ms
fun fractionToDecimal(n: Int, d: Int) = buildString {
if (1L * n.sign * d.sign < 0) append("-")
var n = abs(1L*n); val d = abs(1L*d)
append(n / d); n %= d; if (n > 0L) append(".")
val visited = HashMap<Long, Int>()
while (n > 0L) {
n *= 10; append(n / d); n %= d
visited.put(n, length)?.let {
insert(it, "("); append(")"); n = 0L
}
}
}
// 0ms
pub fn fraction_to_decimal(n: i32, d: i32) -> String {
let (n, d, mut s) = (n as i64, d as i64, String::new());
if n * d < 0 { s.push('-') }; let (n, d) = (n.abs(), d.abs());
s.push_str(&(n/d).to_string()); let mut n = n % d; if n > 0 {s.push('.')};
let mut m = HashMap::new();
while n > 0 {
if let Some(&i) = m.get(&n) { s.insert(i, '('); s.push(')'); break }
m.insert(n, s.len()); n *= 10; s.push_str(&(n/d).to_string()); n %= d
} s
}