Tag Archives: Interview

Problem#1 : Multiply two numbers specified as strings

/**
  A function that multiplies two positive integer numbers stored as strings.

  @Assumptions:
    1) This program does not handle negative numbers. Not even +/- signs.
    2) It will not prune down leading 0's.
    3) The two input strings consist of valid digits only.

  @Algorithm:
    0) Create a result string of size (a.length + b.length).
    1) Take the last untouched digit (least-significant to start with) of one of
       the given numbers (in this case I picked 'b').
    2) Multiply it with all the digits of the other number ('a').
    3) Accumulate the outcome in the result string.
    4) Goto step 1.

*/

#include 

#define INT(c)  ((int)((c) - '0'))
#define CHAR(i) ((char)(i + int('0')))

using namespace std;

string multiply(const string &a, const string &b)
{
  /* initially fill the result string with 0's */
  size_t total_len= a.length() + b.length();
  string result(total_len, '0');

  int num;                                      /* intermediate store */
  int i, j;
  int last_pos_i, last_pos_j, last_pos_k;

  last_pos_i= total_len - 1;

  /* i-loop */
  for (i= b.length() - 1; i >= 0; i --)
  {
    last_pos_j= last_pos_i;

    /* j-loop */
    for (j= a.length() - 1; j >=0; j --)
    {
      last_pos_k= last_pos_j;
      num= INT(a.at(j)) * INT(b.at(i));

      /* k-loop : the actual updation of result string takes place here. */
      while (num)
      {
        num += INT(result.at(last_pos_k));
        result.at(last_pos_k)= CHAR(num % 10);
        /* 'carry' it forward.. ;) */
        num= num / 10;
        last_pos_k --;
      }

      last_pos_j --;
    }

    last_pos_i --;
  }
  return result;
}

int main()
{
  string n1("99");
  string n2("9");
  cout << n1 << " * " << n2 << " = "  << multiply(n1, n2) << endl;
  return 0;
}

Output:

> ./a.out 
99 * 9 = 891