PROBLEM
Link to the Practice Question can be found here
PREREQUISITE
Hash, Mathematics.
DIFFICULTY
Medium-Hard
PROBLEM
You need to find the the fraction of two numbers and print the result in decimal form. You also need to consider the case where the result will be recursively repeated which we denote by bar in mathematics.
EXPLANATION
When does the fractional part repeat ?
Lets simulate the process of converting fraction to decimal. Lets look at the part where we have already figured out the integer part which is floor(numerator / denominator).
Now you are left with ( remainder = numerator%denominator ) / denominator.
If you remember the process of converting to decimal, at each step you do the following :
- multiply the remainder by 10,
- append remainder / denominator to your decimals
- remainder = remainder % denominator.
At any moment, if your remainder becomes 0, you are done.
However, there is a problem with recurring decimals. For example if you look at 1/3, the remainder never becomes 0.
Notice one more important thing.
If you start with remainder = R at any point with denominator d, you will always get the same sequence of digits.
So, if your remainder repeats at any point of time, you know that the digits between the last occurrence of R will keep repeating.
SOLUTION
Solution to the above problem can be found here