Problem statement summary: this is a popular interview question in which you implement a void putlong(long n) function to write the long integer n to the console. To make the problem more challenging, interviewers often impose the following restrictions:
- Only use putchar() and no other functions (ltoa, sprintf, …)
- Do not create a buffer to store the digits
- Do not use a stack as a means to store and reverse the digits
- Do not use recursion
In my first attempt, I reversed the digits order, then extracted them from right to left and printed by means of putchar(). My solution did not work for numbers with trailing zeros such as 1900.
Instead of fixing my code, I approached the problem from a different angle. In my second attempt, I extracted the digits from left to right and that seems to take care of the trailing zeros problem. This solution worked for all of my test cases except when n is equal to long.MinValue(), or -9223372036854775808 (tested with Visual Studion 2005 in 32-bit Windows Vista).
After some debugging, I finally pin-pointed the problem. When n is long.MinValue, and extractor is -1, n / extractor == n because of overflow which prevented us from building the proper extractor, hence the bug (line 14 in the second solution).
To fix this problem, we can initialize the extractor to -10 instead of -1 for n == long.MinValue. Therefore, the expression in line 14 will become:
extractor = n == long.MinValue ? -10 : (n < 0 ? -1 : 1)
For portability, we do not want to rely on long.MinValue, so we can modify the above expression to:
extractor = n < -9 ? -10 : (n < 0 ? -1 : 1)
That should fixes the code. Here is the complete listing:
<div><pre> 1 /// <summary>
2 /// Writes a long number to the console.
3 /// Constraints:
4 /// 1. Use only putchar() and no other means (itoa, sprintf, ...)
5 /// 2. Do not use array to store the digits
6 /// 3. No recursion
7 /// </summary>
8 /// <param name="n">The number to write to the console</param>
9 public static void PutLong(long n)
11 long extractor;
13 // Build the extractor so that (n / extractor) is a single digit [0-9]
14 for (extractor = n < -9 ? -10 : (n < 0 ? -1 : 1);
15 n / extractor >= 10;
16 extractor *= 10)
19 // Case: n is negative.
20 if (n < 0)
23 // Now, we extract the digits starting with the most significant digit
24 // (left-most) and work our way to the least significant digit (right-
25 // most). The number now is always positive because of the previous
26 // block.
27 while (n != 0)
29 char digit = (char)(n / extractor + '0');
31 n %= extractor;
32 extractor /= 10;
35 // take care of trailing zeros: As long as the extractor is not zero,
36 // we are not done. A non-zero extractor means we have trailing zeros.
37 // For example, a 1000 means we need to write out 4 (yes, 4; not 3)
38 // trailing zeros.
39 for (; extractor != 0; extractor /= 10)
As usual, if you have any comment or suggestion, please post them in the comment area or send me private email (see my email right below my picture).