Cel mai mic număr cu suma cifrelor N în C++

Dându-se un număr natural n, vrem să găsim cel mai mic număr natural cu proprietatea că suma cifrelor sale este egal cu n.

Exemplu: Pentru n = 13, răspunsul este 49, cu 4 + 9 = 13 = n.

Algoritm naiv

Un algoritm naiv parcurge toate numerele începând cu 1, verificând pentru fiecare în O(lg(n)) dacă suma cifrelor sale este egală cu n:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim
    int n;
    cin >> n;

    //Căutăm răspunsul
    int i = 1;
    while(true) {
        int copie = i, sumacif = 0;
        while(copie > 0) { //Calculăm suma cifrelor numărului curent, i
            sumacif = sumacif + copie % 10;
            copie = copie / 10;
        }
        if(sumacif == n) { //Am găsit primul număr cum suma cifrelor egală cu n, ne oprim
            cout << i;
            break;
        }
        i++;
    }
    return 0;
}

Algoritm eficient

Să analizăm cum putem să determinăm cel mai mic număr cu suma cifrelor n. Numărul trebuie:

• să aibă cât mai puține cifre;
• primele cifre ale sale să fie cât de mici posibile.

Pentru ca numărul să aibă cât mai puține cifre, trebuie să găsim cifre care să scadă rapid valoarea lui n. Astfel, este clar că ultimele cifre ale răspunsului vor fi cifre de 9, până când nu se mai poate. Diferența rămasă va determina prima cifră a lui răspunsului.

Mai exact, dacă n : 9 = x rest y, mai precis n = 9x + y (prin teorema împărțirii cu rest), atunci numărul răspuns are prima cifră egală cu y, iar următoarele x cifre egale cu 9.

Cu această logică, putem să rezolvăm problema astfel:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim
    int n, raspuns = 0;
    cin >> n;

    //Prima cifră a lui raspuns
    raspuns = n % 9; //n % 9 este y-ul nostru de mai devreme
    for(int i = 1; i <= n / 9; i++) { //n / 9 este x-ul nostru de mai devreme
        raspuns = raspuns * 10 + 9;
    }

    //Afișăm răspunsul
    cout << raspuns;
    return 0;
}

Algoritmul acesta are complexitatea O(n / 9) = O(n).