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)
.
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0