|
Write a program which gives a numerator and a denominator...
Microsoft Interview Questions and Answers
(Continued from previous question...)
20. Write a program which gives a numerator and a denominator...
Question
Write a program which gives a numerator and a denominator, prints the fractional value in a special format. eg. Numerator: 1, Denominator: 3. So Num/Denom = 0.3333333333, but output should be .(3) similarly 0.123123 as .(123) also 0.34232323 as 0.34(23)
maybe an answer:
Any number a / b can be expressed as c + d / b such that d < b.
Now c will the left side of decimal and d / b will be contributing to the right side of decimal. The point to note is that d / b doesn't have any influence on c.
Consider an example 7 / 37. Consider what happens when we multiply it by 10.
70 / 37 = 1 + 33 / 37
So 1 will be the first place after decimal 33 / 37 will only contribute to second place and after.
Multiple by 10 again
330 / 37 = 8 + 34 / 37
So 8 will be the second place after decimal 34 / 37 will only contribute to third place and after.
Whenever a number less than 37 is divided by 37 the remainer can only be any values from 0-36 only 37 possible values so remainer is bound to repeat sometime. If the remainer is 0 we can stop. If the remainder is something we have seen before it will be beginning of the repetition.
Another example.
1 / 8
10 / 8 = 1 + 2 / 8 (so first place 0.1)
20 / 8 = 2 + 4 / 8 (so second place 0.12)
40 / 8 = 5 + 9 / 8 (so third place 0.125 ) remainder is 0 so terminate
Another example
4 / 7
40 / 7 = 35 + 5 / 7 ( so first place is 0.5 )
50 / 7 = 7 + 1 / 7 ( so second place 0.57 )
10 / 7 = 1 + 3 / 7 ( so third place 0.571 )
30 / 7 = 4 + 2 / 7 ( so fourth place 0.5714 )
20 / 7 = 2 + 6 / 7 ( so fifth place 0.57142 )
60 / 7 = 8 + 4 / 7 ( so sixthe place 0.571428 )
40 / 7 == we have encounter this before so it becomes 0.571428571428....
Generating digits of decimal expansion can be done,
e.g., using the following simple algorithm:
void div_periodic(int num, int denom) {
int div = num / denom;
int mod = num % denom;
printf("%d.", div); // print integer part
num = mod;
int niters = 100;
std::vector< int > digits;
while(niters--) {
num *= 10; // num is always smaller than denom
int n_zeros = 0;
while(num < denom) { // add the required number of zeros
num *= 10; n_zeros++;
digits.push_back(0);
}
div = num / denom; // div is always a single digit
mod = num % denom;
digits.push_back(div); // add the next digit
num = mod;
if(num == 0)
break;
}
}
(Continued on next question...)
Other Interview Questions
| 