Đề bài
Số mạnh (strong number) là số bằng tổng giai thừa các chữ số của chính nó. Ví dụ, 145 là số mạnh vì 1! + 4! + 5! = 1 + 24 + 120 = 145. Các nhà toán học gọi những số này là *factorion*; trong hệ thập phân chỉ có đúng bốn số như vậy, nhưng chương trình của bạn cần kiểm tra theo định nghĩa chứ không dựa vào một danh sách có sẵn.
Hãy viết strong_number(n).
Định nghĩa cụ thể như sau: lấy từng chữ số thập phân d của n, cộng d! của tất cả các chữ số đó lại (quy ước 0! = 1), rồi so sánh tổng với n. Vì vậy 0 không phải số mạnh, bởi 0! = 1.
Đầu vào
n: Số cần kiểm tra.
Đầu ra
Trả về true nếu tổng giai thừa các chữ số của n bằng n, ngược lại trả về false.
Ràng buộc
0 ≤ n ≤ 10^9
Ví dụ
Đầu vào:
n = 145
Kết quả mong đợi:
expected = True
Đầu vào:
long long n = 145;
Kết quả mong đợi:
bool expected = true;
Đầu vào:
long n = 145;
Kết quả mong đợi:
bool expected = true;
Giải thích
1! + 4! + 5! = 1 + 24 + 120 = 145, đúng bằng chính số đó, nên kết quả là true.
Đầu vào:
n = 123
Kết quả mong đợi:
expected = False
Đầu vào:
long long n = 123;
Kết quả mong đợi:
bool expected = false;
Đầu vào:
long n = 123;
Kết quả mong đợi:
bool expected = false;
Giải thích
1! + 2! + 3! = 1 + 2 + 6 = 9, mà 9 ≠ 123, nên kết quả là false.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Hãy giữ lại một bản sao của n, vì bạn sẽ thay đổi giá trị đang xử lý khi tách dần các chữ số.
Gợi ý 2
Chỉ cần giai thừa của 0 đến 9, nên hãy tính sẵn chúng một lần.
Gợi ý 3
Kiểm tra xem vòng lặp của bạn làm gì khi n bằng 0: số này có một chữ số.
Độ phức tạp mong đợi
thời gian O(d) với d chữ số, bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.