Grade 9 · Digits of a numberCitește în română

Check digit (digital root)

Original: Cifra de control

O(n)C++1740 lines2 examples

The idea

The check digit is obtained by repeatedly replacing the number with the sum of its digits until a single digit remains (for example 99999 -> 45 -> 9). The formula 1 + (n - 1) % 9 gives the same result for n > 0.

Original description (Romanian)

Cifra de control se obține înlocuind numărul cu suma cifrelor lui, în mod repetat, până când rămâne o singură cifră (de exemplu 99999 -> 45 -> 9). Același rezultat dă formula 1 + (n - 1) % 9, pentru n > 0.

Complexity
O(k), where k is the number of digits of n (after the first sum very few digits remain)
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

99999

Expected output

9
Example 2

Input

1234

Expected output

1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

cifra-de-control.cpp
/*
 * Titlu: Cifra de control
 * Clasa: 9
 * Capitol: Cifrele unui număr
 * Descriere: Cifra de control se obține înlocuind numărul cu suma cifrelor lui,
 *            în mod repetat, până când rămâne o singură cifră
 *            (de exemplu 99999 -> 45 -> 9). Același rezultat dă formula
 *            1 + (n - 1) % 9, pentru n > 0.
 * Complexitate: O(k), unde k este numărul de cifre ale lui n (după prima sumă
 *               rămân foarte puține cifre)
 *
 * Exemplu
 * Intrare: 99999
 * Ieșire: 9
 *
 * Exemplu
 * Intrare: 1234
 * Ieșire: 1
 */
#include <iostream>
using namespace std;

int main()
{
    long long n;
    cin >> n;
    while (n >= 10)
    {
        long long suma = 0;
        while (n > 0)
        {
            suma = suma + n % 10;
            n = n / 10;
        }
        n = suma;
    }
    cout << n << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.