Add Two Big Numbers Represented as Digit Vectors

Reported in interviews at PDT Partners

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.

Related free problems