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...

Related Posts

Related Posts

66. Plus One

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists