Giới thiệu
Trong hướng dẫn này, chúng ta sẽ tính tổng các chữ số của một số liên tục cho đến khi kết quả chỉ còn 1 chữ số (gọi là Digital Root).
Ví dụ
Input: 4543 → 4+5+4+3=16 → 1+6=7
Output: 7
Phương pháp 1: Mô phỏng trực tiếp
#include <bits/stdc++.h>
using namespace std;
void findTheSingleDigit(int n) {
int sum = 0;
while (n > 0 || sum > 9) {
if (n == 0) { n = sum; sum = 0; }
sum += n % 10;
n /= 10;
}
cout << sum << endl;
}
Phương pháp 2: Công thức toán học (O(1))
Digital Root của n:
- n = 0 → 0
- n % 9 == 0 → 9
- Ngược lại → n % 9
void findTheSingleDigit(int n) {
if (n == 0) cout << 0;
else if (n % 9 == 0) cout << 9 << endl;
else cout << n % 9 << endl;
}
Kết quả đầu ra
7
Kết luận
Phương pháp 2 tối ưu O(1) dựa trên tính chất modulo 9. Cả hai cho kết quả giống nhau. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.