PutLong Version 3

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:

  1. Only use putchar() and no other functions (ltoa, sprintf, …)
  2. Do not create a buffer to store the digits
  3. Do not use a stack as a means to store and reverse the digits
  4. 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)
  10 {
  11     long extractor;
  12
  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)
  17         ;
  18
  19     // Case: n is negative.
  20     if (n < 0)
  21         putchar('-');
  22
  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)
  28     {
  29         char digit = (char)(n / extractor + '0');
  30         putchar(digit);
  31         n %= extractor;
  32         extractor /= 10;
  33     }
  34
  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)
  40         putchar('0');
  41 }

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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s