0066. Plus One
- Nhãn: Mảng, Toán học
- Độ khó: Dễ
Đề bài
Mô tả: Cho một mảng số nguyên không âm, mỗi phần tử trong mảng đại diện cho một chữ số của một số nguyên.
Yêu cầu: Tính tổng của số nguyên đó sau khi cộng thêm .
Giải thích:
- .
- .
Ví dụ:
- Ví dụ 1:
- Ví dụ 2:
Ý tưởng
Ý tưởng 1: Mô phỏng
Bài toán này coi toàn bộ mảng như một số nguyên, sau đó cộng thêm . Vấn đề thực chất là sử dụng mảng để mô phỏng phép cộng.
Nếu chữ số hàng đơn vị không phải là , chúng ta chỉ cần cộng thêm vào chữ số hàng đơn vị. Nếu chữ số hàng đơn vị là , chúng ta cần xét trường hợp cần nhớ.
Các bước cụ thể:
- Thêm vào đầu mảng.
- Cộng thêm vào chữ số hàng đơn vị.
- Duyệt qua mảng
- Nếu chữ số tại vị trí đó lớn hơn hoặc bằng , thì tiến sang vị trí tiếp theo và tiếp tục xét nhớ.
- Nếu chữ số tại vị trí đó nhỏ hơn , thì thoát khỏi vòng lặp.
Ý tưởng 1: Cài đặt
Ý tưởng 1: Độ phức tạp
- Độ phức tạp thời gian: . Độ phức tạp thời gian của vòng lặp là .
- Độ phức tạp không gian: .