Sum of decimal digit

The following was a programming interview practice question.

What is the smart way to handle this?

A number M is stored in an array in the reverse order. For example, the number 274 is stored in the follow开发者_Go百科ing array:

A[0]= 4 A[1]=7 A[2]=2

Write a function that given the array A representing some number, returns the sum of the digits of a decimal representation of the number M * 17. Array size can be very large (more than 2,000,000 elements).

Imagine you were multiplying 153 by 17 in longhand. It would look something like this:

  153
   17
  ---
   51
  85
 17
 ----
 2601

But you don't actually need to save the complete result; you only need to add the digits as you go along. So after the first step you know the last digit is 1, and you carry 5. Then after the second step you know the second digit is 0, and you carry 9. Then after the third step you know the third digit is 6, and you carry 2. When you run out of digits to multiply you just have to add the digits of the carry. (You can't carry more than 16, so you only have two cases to think about.)

The following code will do this in O(n).

#include <iostream>
#include <vector>

int times_17_dec_digits_sum(const vector<int> &A)
{
    int sum = 0, carry = 0;

    for (int i = 0; i < A.size(); i++) {
        int perdigitsum = A[i]*17+carry;
        sum += perdigitsum % 10;
        carry = perdigitsum / 10;
    }

    return sum + carry;
}

int main()
{
    std::vector<int> b;
    b.push_back(3);
    b.push_back(5);
    b.push_back(1);

    std::cout << times_17_dec_digits_sum(b) << std::endl;

    return 0;
}

since you add all the digits after you multiply by 17, you can calculate the digits sum whlie going over each element:

17*3 = 51 => 5+1 = 6
17*5 = 85 => 8+5 = 13 
17*1 = 17 => 1+7 = 8

6 + 13 + 8 = 27 => 2+7=9

Three tricks:

• instead of 17 x, use (10 + 8 -1)x; then
• instead of 10 x, shift places; then
• instead of 8 x, bit shift.

E.g:

17 * [3,5,1] = 
7 * [3,5,1,0] + [0,3,5,1] = 
[3,5,1,0]<<3 - [3,5,1,0] + [0,3,5,1]

These are all very fast operations that you can perform element-wise:

A[i] = A[i]<<3 - A[i] + A[i+1];

Decompose (or rather don't compose) the number into the decimal digits. Loop over the container multiplying the element by 17, take the last digit and sum it towards the result, take the rest of the digits as remainder and add it to the result of the multiplication in the next iteration. When the array is completed, add the digits in the remainder to the result.

int times17( const std::vector<int>& a ) {
   int result = 0, remainder = 0;
   for ( std::vector<int>::const_iterator it = a.begin(), end = a.end(); it != end; ++it )
   {
      int tmp = 17* *it + remainder;
      remainder = tmp / 10;
      result += tmp - remainder*10;
   }
   while ( remainder > 0 ) {
      result += remainder % 10;
      remainder /= 10;
   }
   return result;
}