An interview question:
Given two int N (numerator) and D (denominator), return the fraction in string. if the fraction is repeating, then display the repeating part in bracket.
Example: Input: N=1, D=3 output: 0.[3]
Example: Input: N=2, D=5 output: 0.4
My idea:
get a = N/D with double value.
for part after decimal point, get each digit by x 10 in the process, if find repeating, record the index and insert [] finally.
for part before decimal point, get each digit by / 10
Any better ideas?
thanks
I would avoid using a double like the plague. Due to finite precision, it will not give you the correct answer. Stick to integer arithmetic and simulate long division, keeping track of the remainder. After you run out of digits in the numerator (so you are bringing down zeros), also keep a history of remainders and if you see a remainder that is already in the history, that tells you that you have hit a repeating sequence. You can then construct the bracketed output part. (If you hit a zero remainder, of course, that means that the answer is a terminating fraction.)
Here is a rust solution which simulates long division for the fractional part.
There will only be a repeating decimal if the divisor has a factor other than 2 and 5. We can easily check for this by repeatedly dividing by 2 until all factors of 2 are removed and then repeatedly dividing by 5 until all factors of 5 are removed. After dividing, if the resultant number is 1, then there will be no repeating decimal.
To handle the case for the repeating decimal, we keep a hashset of the remainders we have seen until now. If a remainder reappears, we stop the computation.
#[allow(unused_variables)]
use std::collections::HashSet;
use std::io;
fn main() {
let a = read_usize();
let b = read_usize();
println!("{}", long_division(a, b));
}
fn read_usize() -> usize {
let mut input_string = String::new();
io::stdin()
.read_line(&mut input_string)
.expect("failed to read from stdin");
let trimmed = input_string.trim();
let num = trimmed.parse::<usize>().unwrap();
num
}
fn repeating_decimal(denominator: usize) -> bool {
let mut d = denominator;
while d % 2 == 0 {
d /= 2;
}
while d % 5 == 0 {
d /= 5;
}
if d == 1 { false } else { true }
}
fn long_division(a: usize, b: usize) -> String {
let q = a / b;
let r = (a % b) * 10;
if r == 0 {
return q.to_string();
}
if repeating_decimal(b) {
format!("{}.({})",q,divide_repeating_decimal(r, b))
} else {
format!("{}.{}",q,divide_without_repeating_decimal(r, b))
}
}
fn divide_repeating_decimal(mut r: usize, b: usize) -> String {
let mut result = String::new();
let mut seen: HashSet<usize> = HashSet::new();
loop {
if r < b {
r *= 10;
result.push_str(&"0".to_owned());
continue;
}
let q = r / b;
r = (r % b) * 10;
result.push_str(&q.to_string());
if seen.contains(&r) {
break;
}
seen.insert(r.clone());
}
result
}
fn divide_without_repeating_decimal(mut r: usize, b: usize) -> String {
let mut result = String::new();
while r != 0 {
if r < b {
r *= 10;
result.push_str(&"0".to_owned());
continue;
}
let q = r / b;
r = (r % b) * 10;
result.push_str(&q.to_string());
}
result
}
For fixed point, simply multiply the numerator with 10 before dividing. For floating point, simply use division then modf to get the fractional part. In either case, convert to string then format as preferred (1 decimal).
In C you could do something generic that handles either fixed or floating point, by use of _Generic.
A simple example without any error handling:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
char* strfract_int (char* dst, int n, int d)
{
sprintf(dst, "0.%d", n*10 / d);
return dst;
}
char* strfract_double (char* dst, double n, double d)
{
double dummy;
sprintf(dst, "%.1f", modf(n/d, &dummy) );
return dst;
}
#define strfract(dst, n, d) \
_Generic((n), \
int: strfract_int, \
double: strfract_double)(dst,n,d) \
int main (void)
{
char buf [100];
puts( strfract(buf, 1, 3) );
puts( strfract(buf, 2, 5) );
puts( strfract(buf, 1.0, 3.0) );
puts( strfract(buf, 2.0, 5.0) );
}
In a rugged program, check for division against zero, the result of malloc etc etc.
