66. Plus One

Problem

Bài toán yêu cầu tăng giá trị của một số nguyên lớn, được biểu diễn dưới dạng mảng các chữ số (mỗi phần tử là một chữ số), lên 1 và return về mảng kết quả

Approach

Duyệt mảng từ phải → trái (từ chữ số ít ý nghĩa nhất)

Tăng chữ số hiện tại lên 1

Nếu chữ số sau khi tăng < 10, return kết quả ngay (không cần xử lý “carry”)

Nếu chữ số là 10, đặt nó về 0 và tiếp tục cộng “nhớ” cho chữ số bên trái

Nếu duyệt hết mảng mà vẫn còn “nhớ” (tức là toàn bộ các chữ số đều là 9), thêm 1 vào đầu mảng

Time and space complexity

TC: O(n)

SC: O(1)

Solution

typescripttypescript

1function plusOne(digits: number[]): number[] {
2    for (let i = digits.length - 1; i >= 0; i--) {
3        digits[i]++;
4        if (digits[i] < 10) return digits;
5        digits[i] = 0
6    }
7    return [1, ...digits]
8};

💡

Tóm tắt

Tăng chữ số cuối cùng lên 1

Nếu không bị tràn, return về kết quả

Nếu bị tràn (tức là chữ số thành 10), đặt về 0 và tiếp tục cộng “nhớ”

Nếu duyệt hết mà vẫn còn “nhớ”, thêm 1 vào đầu mảng

Loading content...