Đề bài
Mỗi số được cho dưới dạng chuỗi chữ số thập phân và có thể dài tới 60 chữ số, vượt xa sức chứa của số nguyên 64 bit. Hãy cộng tất cả lại và trả về tổng chính xác. Đây chính là phép cộng cột dọc ở trường: cộng các chữ số từ phải sang trái và nhớ sang cột tiếp theo.
Hãy viết sum_of_big_numbers(numbers).
Đầu vào
numbers: Các số nguyên không âm viết dưới dạng chuỗi chữ số, không có số 0 ở đầu (riêng số không là "0").
Đầu ra
Trả về tổng chính xác dưới dạng chuỗi chữ số không có số 0 ở đầu. Danh sách rỗng có tổng là "0".
Ràng buộc
0 ≤ numbers.length ≤ 100; mỗi số có từ 1 đến 60 chữ số
Ví dụ
Đầu vào:
numbers = ["999", "1"]
Kết quả mong đợi:
expected = "1000"
Đầu vào:
std::vector<std::string> numbers = {"999", "1"};
Kết quả mong đợi:
std::string expected = "1000";
Đầu vào:
string[] numbers = new string[] {"999", "1"};
Kết quả mong đợi:
string expected = "1000";
Giải thích
Cộng 1 vào 999 thì phải nhớ qua mọi cột: "1000".
Đầu vào:
numbers = ["98765432109876543210", "12345678901234567890"]
Kết quả mong đợi:
expected = "111111111011111111100"
Đầu vào:
std::vector<std::string> numbers = {"98765432109876543210", "12345678901234567890"};
Kết quả mong đợi:
std::string expected = "111111111011111111100";
Đầu vào:
string[] numbers = new string[] {"98765432109876543210", "12345678901234567890"};
Kết quả mong đợi:
string expected = "111111111011111111100";
Giải thích
Cộng từng cột, hai số 20 chữ số cho kết quả "111111111011111111100", dài hơn mỗi số hạng một chữ số.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Xếp các số thẳng hàng theo chữ số cuối cùng.
Gợi ý 2
Cộng từng cột một, giữ phần nhớ cho cột tiếp theo.
Gợi ý 3
Khi đã cộng xong mọi cột, phần nhớ còn lại trở thành các chữ số mới ở đầu.
Độ phức tạp mong đợi
thời gian O(total digits), bộ nhớ phụ O(max length)
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.