Cho số nguyên không âm dưới dạng mảng chữ số A (ví dụ: 534 → [5,3,4]). Cộng thêm số nguyên K. Trả về kết quả cũng dạng mảng chữ số.
Ví dụ: A=[5,3,4], K=78 → 534+78=612 → [6,1,2].
Thuật toán 1: Chuyển sang số (Đơn giản, Python hỗ trợ big int)
class Solution(object):
def addToArrayForm(self, A, K):
num = int(''.join(map(str, A)))
total = num + K
return [int(d) for d in str(total)]
ob1 = Solution()
print(ob1.addToArrayForm([5,3,4], 78)) # [6, 1, 2]
Thuật toán 2: Cộng trực tiếp trên mảng (O(n), không cần big int)
Mô phỏng phép cộng cột từ phải sang trái:
class Solution(object):
def addToArrayForm(self, A, K):
i = len(A) - 1
carry = 0
res = []
while i >= 0 or K > 0 or carry:
digit_a = A[i] if i >= 0 else 0
digit_k = K % 10
K //= 10
total = digit_a + digit_k + carry
res.append(total % 10)
carry = total // 10
i -= 1
return res[::-1]
ob1 = Solution()
print(ob1.addToArrayForm([5,3,4], 78)) # [6, 1, 2]
print(ob1.addToArrayForm([2,7,4], 181)) # [4, 5, 5]
print(ob1.addToArrayForm([9,9,9,9,9,9,9,9,9,9], 1)) # [1,0,0,0,0,0,0,0,0,0,0]
Độ phức tạp
- Cách 1 (Python big int):
O(n)time,O(n)space - đơn giản, Python native - Cách 2 (Manual):
O(max(n, log K))time,O(max(n, log K))space - dùng cho ngôn ngữ không có big int
Đầu vào / Đầu ra
Input: A = [5,3,4], K = 78 Output: [6,1,2]