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

Largest number formed from the digits of n

Original: Cel mai mare număr format cu cifrele lui n

O(n)C++1743 lines2 examples

The idea

We count how many times each digit appears, in a frequency array with 10 positions (frecv[c] = how many times digit c appears). The largest number is obtained by writing the digits from 9 down to 0, each as many times as it appears.

Original description (Romanian)

Numărăm de câte ori apare fiecare cifră, într-un vector de frecvență cu 10 poziții (frecv[c] = de câte ori apare cifra c). Cel mai mare număr se obține scriind cifrele de la 9 spre 0, fiecare de câte ori apare.

Complexity
O(k), where k is the number of digits of n
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

31415

Expected output

54311
Example 2

Input

1020

Expected output

2100

The code

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

cel-mai-mare-numar-din-cifre.cpp
/*
 * Titlu: Cel mai mare număr format cu cifrele lui n
 * Clasa: 9
 * Capitol: Cifrele unui număr
 * Descriere: Numărăm de câte ori apare fiecare cifră, într-un vector de
 *            frecvență cu 10 poziții (frecv[c] = de câte ori apare cifra c).
 *            Cel mai mare număr se obține scriind cifrele de la 9 spre 0,
 *            fiecare de câte ori apare.
 * Complexitate: O(k), unde k este numărul de cifre ale lui n
 *
 * Exemplu
 * Intrare: 31415
 * Ieșire: 54311
 *
 * Exemplu
 * Intrare: 1020
 * Ieșire: 2100
 */
#include <iostream>
using namespace std;

int main()
{
    long long n, rez = 0;
    int frecv[10] = {0};
    cin >> n;
    do
    {
        frecv[n % 10]++;
        n = n / 10;
    }
    while (n > 0);
    for (int c = 9; c >= 0; c--)
    {
        for (int i = 1; i <= frecv[c]; i++)
        {
            rez = rez * 10 + c;
        }
    }
    cout << rez << '\n';
    return 0;
}

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