On computing the checksum


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){
        sum += index *(c-'0');
    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;
    return sum%10;

Loop invariant:

Once again N is the length of the string.


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

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

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Algorithm, C++, Software Puzzle. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s