Add Two Numbers

mediumFREELinked ListsMeta DSA

Given two non-negative integers represented as arrays of digits in reverse order (least significant digit first), return their sum as an array in the same reverse order.

Each element contains a single digit. The numbers do not have leading zeros except the number 0 itself.

Output as space-separated digits.

Example

Input

2,4,3
5,6,4

Output

7 0 8

Reasoning

l1 and l2 are the digits of two whole numbers, ones digit first: position $k$ holds the coefficient of $10^k$ . So $[2, 4, 3]$ means $2 + 4 \cdot 10 + 3 \cdot 10^2 = 342$ , and $[5, 6, 4]$ means $465$ .
The answer is just $342 + 465 = 807$ , written back in the same ones-first layout: $807 = 7 + 0 \cdot 10 + 8 \cdot 10^2$ , giving 7 0 8.
Look at each power of ten: ones $2 + 5 = 7$ ; tens $4 + 6 = 10$ , which is not a single digit, so the tens place keeps $0$ and the extra $10 \cdot 10 = 100$ moves up to the hundreds; hundreds $3 + 4 + 1 = 8$ .
Notice the sum can have more digits than either input: $9999999 + 9999 = 10009998$ comes out as 8 9 9 9 0 0 0 1, eight digits from inputs of seven and four.
The inputs may also differ in length; a missing position simply contributes $0$ .

Constraints

1 <= len(l1), len(l2) <= 100
0 <= l1[i], l2[i] <= 9

More from Meta DSA

Valid Palindrome IIeasy Dot Product of Two Sparse Vectorseasy Random Pick with Weightmedium Copy List with Random Pointermedium Remove Nth Node From Endmedium

Concept primer

Background Knowledge

The problem involves working with linked lists, but in this case, the linked lists are represented as arrays of digits. Each digit in the array represents a node in the linked list, and the digits are in reverse order, meaning the least significant digit comes first. This is a common representation for numbers in programming, especially when working with large integers. Understanding how to manipulate and perform operations on these arrays is crucial to solving the problem.

To approach this problem, it's essential to have a solid grasp of basic arithmetic operations, particularly addition, and how to handle carry-over values. In the context of linked lists, this means being able to iterate through the arrays, add corresponding digits, and manage any carry-over values that may arise. Additionally, familiarity with array indexing and looping constructs will be necessary to implement the solution.

The problem also touches on the concept of dynamic array sizing, as the resulting sum may have a different number of digits than the input arrays. This means being able to handle arrays of varying lengths and adjusting the output array accordingly. By understanding these key concepts, you'll be well-equipped to tackle the problem and develop an effective solution.

Algorithm/Approach

The general approach to solving this problem involves using a simple iterative method to add corresponding digits from the input arrays, while managing any carry-over values that may arise. This can be achieved by using a two-pointer technique, where two pointers iterate through the input arrays, adding corresponding digits and updating the carry-over value as needed. The result is then stored in a new array, which is returned as the sum of the input numbers.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an empty array to store the result
Initialize a carry-over value to 0
Iterate through the input arrays, adding corresponding digits and updating the carry-over value as needed
Store the result of each addition in the result array
If a carry-over value remains after iterating through the input arrays, append it to the result array
Return the result array as the sum of the input numbers

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Forgetting to handle carry-over values correctly
Not adjusting the result array size correctly to accommodate the sum
Not iterating through the input arrays correctly, potentially leading to incorrect results

Time & Space Complexity

The expected time complexity for this problem is O(max(n, m)), where n and m are the lengths of the input arrays. This is because we need to iterate through the input arrays once to perform the addition. The expected space complexity is also O(max(n, m)), as we need to store the result in a new array. In the worst-case scenario, the result array may have a length of max(n, m) + 1, where the extra element is the carry-over value.

solution.py

Python 3.13

Test results