Problem overview
The function add_two_numbers receives two vectors of digits, list1 and list2. Each vector stores one non-negative integer with the digits in reverse order: the first element is the ones digit, the second is the tens digit, and so on. The function returns the sum in the same format, as a new Vec<i32>. Neither number has leading zeros, except the number 0 itself.
For [2, 4, 3] and [5, 6, 4] the numbers are 342 and 465. Their sum is 807, so the result is [7, 0, 8]. For [9, 9, 9, 9, 9, 9, 9] and [9, 9, 9, 9] the numbers are 9999999 and 9999. The sum is 10009998, stored as [8, 9, 9, 9, 0, 0, 0, 1]. Here the result has one more digit than either input.
Approach: add column by column, like on paper
Reverse order makes this problem easy. The ones digits come first, which is exactly where school addition starts. Work through the columns from left to right in the vectors:
- Add the digit of each number in this column, plus the carry from the previous column.
- The new digit is that sum modulo 10. The new carry is the sum divided by 10, which is 0 or 1.
- Move to the next column.
Two details need care. The numbers can have different lengths, and a number that has run out of digits counts as 0 in the remaining columns. And a carry can be left over after both numbers are used up, as with 5 + 5, which needs a second digit. The loop must keep going while a carry remains.
On [2, 4, 3] and [5, 6, 4]: the first column is 2 + 5 = 7, with no carry, so the digit is 7. The second is 4 + 6 = 10, so the digit is 0 and the carry is 1. The third is 3 + 4 + 1 = 8, so the digit is 8. Both vectors are exhausted and the carry is 0, so the loop stops. The result is [7, 0, 8].
Step by step
- Create
carry.let mut carry = 0i32;starts at 0. Thei32suffix gives the literal the same type as the digits. - Create
result. An emptyVec::new(). Its element type is inferred when the first digit is pushed. - Create two indices,
iandj, asusizestarting at 0. Rust indexes vectors withusize. - Loop while
i < list1.len() || j < list2.len() || carry > 0. The third condition is what keeps the final carry from being lost. - Seed the column sum with
let mut digit_sum = carry;, so the previous column's overflow counts first. - Add each number's digit if it has one. If
i < list1.len(), addlist1[i]and incrementi. Do the same forlist2withj. The checks are separate, because the numbers may differ in length. - Update the carry with
carry = digit_sum / 10. Integer division drops the remainder, so this is 1 when the sum is 10 or more and 0 otherwise. - Reduce the sum to one digit with
digit_sum %= 10. - Push the digit onto
result. The output stays in reverse order, like the inputs. - Return
resultas the last expression.
The solution in Rust
struct Solution;
impl Solution {
fn add_two_numbers(list1: Vec<i32>, list2: Vec<i32>) -> Vec<i32> {
let mut carry = 0i32;
let mut result = Vec::new();
let mut i = 0usize;
let mut j = 0usize;
while i < list1.len() || j < list2.len() || carry > 0 {
let mut digit_sum = carry;
if i < list1.len() {
digit_sum += list1[i];
i += 1;
}
if j < list2.len() {
digit_sum += list2[j];
j += 1;
}
carry = digit_sum / 10;
digit_sum %= 10;
result.push(digit_sum);
}
result
}
}
Rust details worth knowing:
- Literal suffixes.
0i32and0usizeare the number 0 with the type spelled out. Without a suffix, Rust infers the type from how the variable is used, and falls back toi32if nothing decides.iandjindex vectors, so they must beusize, and the suffix states that directly. - Vectors in this lesson. The inputs are already vectors of digits, so there are no nodes to follow. The same algorithm works on a linked list by advancing node pointers instead of indices.
- The element type of
resultcomes fromresult.push(digit_sum), ani32, and from the function's return typeVec<i32>. - Integer division.
/on two integers truncates.13 / 10is 1 and9 / 10is 0. For these non-negative numbers,%gives the last digit. ||short-circuits. The loop condition is made of comparisons, so each part is abool. Rust does not treat a number as true or false, socarryalone would not compile as a condition.- No overflow. The largest possible column sum is 9 + 9 + 1 = 19, which fits easily in an
i32.
Complexity
Time: O(max(m, n)), where m and n are the lengths of the two inputs. The loop runs once per column: the longer length, plus at most one extra pass for a final carry.
Space: O(max(m, n)). The result holds one digit per column, which is required output, and the other variables are constant in size.
Edge cases and common mistakes
- Different lengths.
[1, 8]plus[0]gives[1, 8]. The second vector is exhausted after one column and contributes nothing after that. - A final carry.
[5]plus[5]gives[0, 1]. Withoutcarry > 0in the loop condition, the answer would be[0]. - A carry that ripples. The 9s example produces a carry in every column, which is why the result is longer than both inputs.
- Zero.
[0]plus[0]gives[0]. - Forgetting the old carry. If
digit_sumstarts at 0 instead ofcarry, carries vanish and the carry out of one column is never added into the next, so a sum like 5 + 5 with a carry, or 4 + 6 in the middle of a number, comes out wrong. - Reading past the end. Indexing
list1[i]withi == list1.len()panics with "index out of bounds", which is why each addition is guarded by its ownif. - Reversing the output. Both inputs and the output use reverse digit order, so nothing needs reversing.
Testing
[2, 4, 3]and[5, 6, 4]give[7, 0, 8].[9, 9, 9, 9, 9, 9, 9]and[9, 9, 9, 9]give[8, 9, 9, 9, 0, 0, 0, 1].[0]and[0]give[0].[5]and[5]give[0, 1].[1, 8]and[0]give[1, 8].
