Week 2

Implicit casting

Modulo operator

If $a$ and $b$ are integers, then $$ a = q \times b + r, $$ where $q$ is the quotient and $r$ is the remainder in the division of $a$ by $b$. Similarly, if $\mathtt{a}$ and $\mathtt{b}$ are $\mathtt{int}$s in C++, then $$ \mathtt{a} = \mathtt{a/b} \times \mathtt{b} + \mathtt{a \% b}, $$ in C++.

A consequence of this is that $\mathtt{a \% b}$ will have the same sign as $\mathtt{a}$.

Exercise 2.1

Write a program that takes an integer as input from the user and outputs

0

if the integer is even and

1

if the integer is odd.

Solution

#include <iostream>

using namespace std;

int main() {
    int input;

    cin >> input;
    cout << (input % 2) * (input % 2) << '\n';

    return 0;
}

Note that simply using

    cout << input % 2 << '\n';

would not give the correct result for negative integer inputs.

Alternative solution 1

#include <iostream>

using namespace std;

int main() {
    int input;

    cin >> input;

    bool output = input % 2;

    cout << output << '\n';

    return 0;
}

Alternative solution 2

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int input;

    cin >> input;
    cout << abs(input % 2) << '\n';

    return 0;
}

ISBN-13

The ISBN-13 (International Standard Book Number) of a book is a 13-digit number (often located on the back of the book) that encodes information about the book (e.g., country, publisher). If $d_1, d_2, \dots, d_{13}$ are the digits of the ISBN-13, then the last digit $d_{13}$ is chosen such that the checksum $$ d_1 + 3d_2 + d_3 + 3d_4 + \dots + d_{11} + 3d_{12} + d_{13} $$ modulo $10$ is equal to $0$.

Exercise 2.2

Given that the first 12 digits of an ISBN-13 are 978111940297, what must the last digit be?

Solution

The last digit must be 8.

Bonus

Which book has this ISBN-13? 😉

Exercise 2.3

Write a program that prompts the user for the first 12 digits of an ISBN-13 and outputs the 13^th digit.

For example, if the user enters

978030640615

the program should output

7

and if the user enters

978006065292

the program should output

0

Solution

Here is one possible solution, using strings and characters.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string isbn;

    cout << "Enter the first 12 digits of the ISBN-13: ";
    cin >> isbn;

    int odd_sum = isbn[0] + isbn[2] + isbn[4] +
                  isbn[6] + isbn[8] + isbn[10] - 6 * '0';

    int even_sum = isbn[1] + isbn[3] + isbn[5] +
                   isbn[7] + isbn[9] + isbn[11] - 6 * '0';

    cout << "The last digit is: ";
    cout << (10 - (odd_sum + 3 * even_sum) % 10) % 10 << '\n';

    return 0;
}

Digits and modulo

We observe that the last digit of any nonnegative integer is always equal to that integer modulo 10.

To prove this, suppose that the number has $n$ digits $d_0, d_1, \dots, d_{n-1}$ indexing from right to left (for example, if the number is $2345$, then $n = 4$ and $d_0 = 5$, $d_1 = 4$, $d_2 = 3$, $d_3 = 2$). Then the number is equal to $$ d_{n-1} \cdot 10^{n-1} + d_{n-2} \cdot 10^{n-2} + \cdots + d_1 \cdot 10^1 + d_0 \cdot 10^0, $$ which is equal to $$ \definecolor{accent}{RGB}{47, 142, 194} {\color{accent} (d_{n-1} \cdot 10^{n-2} + d_{n-2} \cdot 10^{n-3} + \cdots + d_1 \cdot 10^0) \cdot 10} + d_0. $$ Since ${\color{accent} (d_{n-1} \cdot 10^{n-2} + d_{n-2} \cdot 10^{n-3} + \cdots + d_1 \cdot 10^0) \cdot 10}$ is a multiple of 10 and $0 \leq d_0 < 10$, the remainder of the division of the number by 10 must equal $d_0$, which is the last (i.e., rightmost) digit.