## Problem

Marius Bancila [Bancila 2018](Chapter 8, Problem 69) describes a checksum computation problem which can be paraphrased as follows:

Let X = x_{1}x_{2}…x_{N}

where x_{i} is a decimal digit.

X is a valid number if

(Σ_{i=0}^{N} (N-i+1)*x_{i}) 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

x_{1} +

x_{1} + x_{2} +

...

x_{1} + x_{2} + ... + x_{N}

Notice that x_{1} is added N times, x_{2} 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.