Đề bài
Đánh số các chữ số của n từ trái sang, bắt đầu từ 1, nâng mỗi chữ số lên lũy thừa bằng vị trí của nó rồi cộng các kết quả lại. Nếu tổng thu được đúng bằng n thì đó là số Disarium. Ví dụ, với 175 ta có 1¹ + 7² + 5³ = 1 + 49 + 125 = 175.
Hãy viết disarium_number(n).
Đầu vào
n: Số cần kiểm tra.
Đầu ra
Trả về true nếu n là số Disarium, ngược lại trả về false. Mọi số có một chữ số đều là số Disarium.
Ràng buộc
1 ≤ n ≤ 10^9
Ví dụ
Đầu vào:
n = 89
Kết quả mong đợi:
expected = True
Đầu vào:
long long n = 89;
Kết quả mong đợi:
bool expected = true;
Đầu vào:
long n = 89;
Kết quả mong đợi:
bool expected = true;
Giải thích
8¹ + 9² = 8 + 81 = 89, nên kết quả là true.
Đầu vào:
n = 98
Kết quả mong đợi:
expected = False
Đầu vào:
long long n = 98;
Kết quả mong đợi:
bool expected = false;
Đầu vào:
long n = 98;
Kết quả mong đợi:
bool expected = false;
Giải thích
9¹ + 8² = 9 + 64 = 73 chứ không phải 98, 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
Vị trí được đếm từ bên trái, nên hãy đổi n thành chuỗi hoặc đếm số chữ số trước.
Gợi ý 2
Tính lũy thừa bằng phép nhân số nguyên thay vì dùng hàm số thực.
Gợi ý 3
Số hạng lớn nhất là 9^10, vừa thoải mái trong 64 bit.
Độ phức tạp mong đợi
thời gian O(d^2) 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.