Add Two Big Numbers Represented as Digit Vectors
Problem statement
You are given two non-negative integers represented as vectors of decimal digits, most significant digit first. For example, the number $1234$ is stored as $[1, 2, 3, 4]$ and the number $39$ is stored as $[3, 9]$. Each entry is a single digit in $\{0, 1, \ldots, 9\}$.
Return the sum of the two numbers as a digit vector in the same most-significant-first format. This is the array version of the classic linked-list "add two numbers" problem: the numbers can be far larger than a 64-bit integer can hold, so you must add them digit by digit rather than by converting to a native integer type.
Constraints:
- $1 \le \text{len}(num1),\ \text{len}(num2) \le 10^{5}$
- Each digit is in $\{0, 1, \ldots, 9\}$.
- Both inputs are big-endian (index $0$ is the most significant digit) and contain no leading zeros, except that the single vector $[0]$ represents the number zero.
Example 1:
Input: num1 = [1,2,3,4], num2 = [3,9]
Output: [1,2,7,3]
Explanation: 1234 + 39 = 1273.
Example 2:
Input: num1 = [9,9], num2 = [1]
Output: [1,0,0]
Explanation: 99 + 1 = 100. The carry propagates past the front, so the result is one digit longer than the longer input.
Example 3:
Input: num1 = [0], num2 = [0]
Output: [0]
Explanation: 0 + 0 = 0.Show hint
How would you add these two numbers by hand on paper, and which end of each vector does that start from?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.