Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Cộng số lớn

Cộng một danh sách các số quá dài so với mọi kiểu số nguyên có sẵn.

Bạn sẽ học được gì

  • Cộng các số lưu dưới dạng chuỗi chữ số
  • Xử lý phần nhớ giữa các cột
  • Bỏ các số 0 ở đầu kết quả

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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".

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.