## Problem

Marius Bancila [Bancila 2018](Chapter 8, Problem 69) describes a checksum computation problem which can be paraphrased as follows:
Let X = x1x2…xN
where xi is a decimal digit.
X is a valid number if

i=0N (N-i)*xi) mod 10 = 0

## Naive Solution

A function to compute the checksum is shown below in C++ syntax

```int checksum(const string& number)
{
auto index = number.length();
auto sum = 0;
auto K = -1;
for(auto c: number){
++K;
sum += index *(c-'0');
--index;
}
return sum%10;
}

```

Loop invariant:

Here K is the index of the loop and N is the length of the string. Notice that K is redundant and included only for the purpose of the proof

However one could avoid the multiplication by using the following routine:

```int my_checksum(const string& number)
{
auto s0 = 0;
auto sum = 0;
auto K = 0;
for(auto c: number){
s0 += (c - '0');
sum +=  s0;
++K;
}
return sum%10;
}
```

Loop invariant:

Once again N is the length of the string.

## Explanation

In case the correctness of the solution is not obvious, notice that the `sum` can be computed as follows

``` x1 + x1 + x2 + ... x1 + x2 + ... + xN ```

Notice that x1 is added N times, x2 is added N-1 times and so on. Thus in `my_checksum, s0` computes a single row while `sum` accumulates all the rows computed

Reference
[Bancila 2018] Marius Bancila “The Modern C++ Challenge” Packt Publishing Birmingham-Mumbai 2018.