Đề bài
Lũy thừa của 2 tăng rất nhanh: 2^64 đã có 20 chữ số, còn 2^2000 có hơn 600 chữ số. Hãy tính chính xác 2^n và cộng các chữ số thập phân của nó. Nếu ngôn ngữ không có số nguyên lớn, hãy lưu số dưới dạng mảng (array) các chữ số và nhân đôi n lần.
Hãy viết digit_sum_power_of_two(n).
Đầu vào
n: Số mũ.
Đầu ra
Trả về tổng các chữ số thập phân của 2^n.
Ràng buộc
0 ≤ n ≤ 2000
Ví dụ
Đầu vào:
n = 10
Kết quả mong đợi:
expected = 7
Đầu vào:
long long n = 10;
Kết quả mong đợi:
long long expected = 7;
Đầu vào:
long n = 10;
Kết quả mong đợi:
long expected = 7;
Giải thích
2^10 = 1024 và 1 + 0 + 2 + 4 = 7.
Đầu vào:
n = 0
Kết quả mong đợi:
expected = 1
Đầu vào:
long long n = 0;
Kết quả mong đợi:
long long expected = 1;
Đầu vào:
long n = 0;
Kết quả mong đợi:
long expected = 1;
Giải thích
2^0 = 1, nên tổng chữ số là 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
2^n là 1 nhân đôi n lần.
Gợi ý 2
Lưu chữ số theo thứ tự chữ số thấp nhất trước, để phần nhớ dịch dần về cuối mảng.
Gợi ý 3
Chỉ cộng các chữ số sau khi đã nhân đôi xong.
Độ phức tạp mong đợi
thời gian O(n²), bộ nhớ phụ O(n)
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.