How to find K first digits of the decimal representation of 1/N

Question

This is an interview question I came across: find K first digits of the decimal representation of 1/N. It looks like we need just calculate 10^K/N to solve the problem. Does it make sense ? It looks like I am missing something because the solution is too easy.

Answer 1

Just implement grade-school long division:

int value = 1;
bool outputDecimalSeparator = false;
int digitsOutput = 1;
while(digitsOutput <= k) {
    if (value == 0) {
        Console.Write(0);
    }
    else {
        if (value < n) {
            Console.Write(0);
            value *= 10;
        }
        else {
            Console.Write(value / n);  
            value %= n;
        }
   }
   if (outputDecimalSeparator == false) {
       outputDecimalSeparator = true;
       Console.Write('.');
   }
   digitsOutput++;
}
Console.WriteLine();

The branch on value == 0 is to detect when 1 / n has a terminating representation of less than k digits.

Here, n is the denominator in 1 / n and k is the number of digits to print in the decimal representation of 1 / n.

Note that by changing value *= 10 to value *= b you can print the b-ary representation of 1 / n as well.

Answer 2

Calculating 10^K/N can be extremely costly with large K's and small N's.

This is probably closer to a good solution: long division. It's how we used to divide numbers before calculators. :)

Obviously, you should only perform this algorithm until it yields K digits.

Answer 3

If it is first k digits, isn't it very straight forward to multiply the numerator by 10^k and so it becomes easier to divide by N? And if we need the answer, the decimal representation that is, then we will end up the dividing the result by 10^K again so that previous multiplication nullifies.