Decimal Digit Amount

Question

The next was the question of the practice of interviewing with programming.
What is the smart way to handle this?

The number M is stored in the array in the reverse order. For example, number 274 is stored in the following array:

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

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

Answer 1

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; } 

Answer 2

Imagine that you multiplied 153 by 17 in a long channel. It will look something like this:

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

But you really don't need to keep the full result; you only need to add numbers as you move. So, after the first step, you know that the last digit is 1, and you carry 5. Then, after the second step, you know that the second digit is 0, and you carry 9. Then, after the third step, you know that the third the number is 6, and you carry 2. When you run out of numbers to multiply, you just need to add the carry numbers. (You cannot wear more than 16, so you only need to have two cases.)

Answer 3

since you add all the numbers after multiplying by 17, you can calculate the sum of the numbers passing through 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 

Answer 4

Three tricks :

• instead of 17 x , use (10 + 8 -1)x ; then
• instead of 10 x , the shift point; then
• instead of 8 x , shift bits.

eg:

 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 quick operations that you can perform on elements:

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

Answer 5

Expand (or rather do not make up) the number in decimal digits. Turn the container over, multiplying the element by 17, take the last digit and sum it by the result, take the remaining digits as the remainder and add it to the multiplication result in the next iteration. When the array is complete, add the numbers to the remainder of 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; }