Search code examples
c++algorithmvectorstdmultiplication

How to multiply std::vector<int> by int where vector's each element should be one digit?


I have a class, call it 'BigNumber', which has a vector v field.
Each element should be one digit.
I want to implement a method to multiply this vector by an integer, but also keep elements one digit.
E.g: <7,6> * 50 = <3,8,0,0>
The vector represents a number, stored in this way.
In my example, <7,6> is equal to 76, and <3,8,0,0> is 3800.
I tried the following, but this isn't good (however it works), and not the actual solution for the problem.

   //int num, BigNumber bn
    if (num > 0)
  {
    int value = 0, curr = 1;
    for (int i = bn.getBigNumber().size() - 1; i >= 0; i--)
    {
      value += bn.getBigNumber().at(i) * num * curr;
      curr *= 10;
    }
    bn.setBigNumber(value); //this shouldn't be here
    return bn;
  }

The expected algortithm is multiply the vector itself, not with a variable what I convert to this BigNumber.

The way I set Integer to BigNumber:

void BigNumber::setBigNumber(int num)
{
  if (num > 0)
  {
    bigNum.clear();
    while (num != 0)
    {
      bigNum.push_back(num % 10);
      num = (num - (num % 10)) / 10;
    }
    std::reverse(bigNum.begin(), bigNum.end());
  }
  else
  {
    throw TOOSMALL;
  }
};

The method I want to implement:

//class BigNumber{private: vector<int> bigNum; ... }
void BigNumber::multiplyBigNumber(BigNumber bn, int num)
{
  if (num > 0)
  {
    //bn.bigNum * num
  }
  else
  {
    throw TOOSMALL;
  }
}

Solution

  • As this is for a school project, I don't want to just write the code for you. So here's a hint.

    Let's say you give me the number 1234 --- and I choose to store each digit in a vector in reverse. So now I've got bignum = [4, 3, 2, 1].

    Now you ask me to multiply that by 5. So I create a new, empty vector result=[ ]. I look at the first item in bignum. It's a 4.

    4 * 5 is 20, or (as you do at school) it is 0 carry 2. So I push the 0 into result, giving result = [0] and carry = 2.

    Questions for you:

    1. If you were doing this by hand (on paper), what would you do next?
    2. Why did I decide to store the digits in reverse order?
    3. Why did I decide to use a new vector (result), rather than modifying bignum?

    and only after you have a worked out how to multiply a bignum by an int:

    1. How would you multiply two bignums together?