Multiplying a big number by a small number

Original: Înmulțirea unui număr mare cu un număr mic

O(n)C++1778 lines3 examples

The idea

The small number k (at most 10^9) fits in an int, so it does not need to be split into digits. For every digit a[i], from the units, we compute t = a[i] * k + carry (in long long, so we do not overflow); the result digit is t % 10, and the carry becomes t / 10. The carry left at the end may have several digits, so we break it down digit by digit. If k = 0, the result is 0.

Original description (Romanian)

Numărul mic k (cel mult 10^9) încape într-un int, deci nu trebuie despărțit în cifre. Pentru fiecare cifră a[i], de la unități, calculăm t = a[i] * k + transport (în long long, ca să nu depășim); cifra rezultatului este t % 10, iar transportul devine t / 10. Transportul rămas la final poate avea mai multe cifre, așa că îl descompunem cifră cu cifră. Dacă k = 0, rezultatul este 0.

Complexity: O(k1 + c), where k1 is the number of digits of the big number and c the number of digits of k
Grade: Grade 12 (Clasa a XII-a)
Chapter: Big numbers

Examples

Example 1

Input

123456789012345678901234567890 9

Expected output

1111111101111111110111111111010

Example 2

Input

99999999999 1000000000

Expected output

99999999999000000000

Example 3

Input

123456789 0

Expected output

The code

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

inmultirea-cu-un-numar-mic.cpp

/*
 * Titlu: Înmulțirea unui număr mare cu un număr mic
 * Clasa: 12
 * Capitol: Numere mari
 * Descriere: Numărul mic k (cel mult 10^9) încape într-un int, deci nu trebuie
 *            despărțit în cifre. Pentru fiecare cifră a[i], de la unități,
 *            calculăm t = a[i] * k + transport (în long long, ca să nu depășim);
 *            cifra rezultatului este t % 10, iar transportul devine t / 10.
 *            Transportul rămas la final poate avea mai multe cifre, așa că îl
 *            descompunem cifră cu cifră. Dacă k = 0, rezultatul este 0.
 * Complexitate: O(k1 + c), unde k1 este numărul de cifre al numărului mare și c
 *               numărul de cifre al lui k
 *
 * Exemplu
 * Intrare: 123456789012345678901234567890 9
 * Ieșire: 1111111101111111110111111111010
 *
 * Exemplu
 * Intrare: 99999999999 1000000000
 * Ieșire: 99999999999000000000
 *
 * Exemplu
 * Intrare: 123456789 0
 * Ieșire: 0
 */
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> citesteNumar(const string &s)
{
    vector<int> a;
    for (int i = (int)s.size() - 1; i >= 0; i--)
        a.push_back(s[i] - '0');
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
    return a;
}

void afiseazaNumar(const vector<int> &a)
{
    for (int i = (int)a.size() - 1; i >= 0; i--)
        cout << a[i];
    cout << '\n';
}

vector<int> inmultesteMic(const vector<int> &a, long long k)
{
    if (k == 0)
        return vector<int>(1, 0);
    vector<int> c;
    long long transport = 0;
    for (int i = 0; i < (int)a.size(); i++)
    {
        long long t = a[i] * k + transport;
        c.push_back(t % 10);
        transport = t / 10;
    }
    while (transport > 0)
    {
        c.push_back(transport % 10);
        transport /= 10;
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}

int main()
{
    string s;
    long long k;
    cin >> s >> k;
    afiseazaNumar(inmultesteMic(citesteNumar(s), k));
    return 0;
}

Input (stdin)

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