// The new array needs to be at least as large as the largest of the original
// array, but also needs to be one item longer, in case there is a carry in the
// last digit. For example [1] + [9] would yield [1, 0]. Similarly, [9,9,9] + [1]
// would yield [1,0,0,0].
int sum_size = max(array_one.length(), array_two.length()) + 1;
std::vector<int> array_three(sum_size);
// But now our offsets are different. The "last" item of array_three is one past
// the last offset of array_one and array_two. Furthermore, the offsets
// of array_one and array_two might be different if they have different numbers
// of digits. For example, 234 + 6 = [2,3,4] + [6]. For the first one you need to
// start at index 2, for the second you need to start at index 0. In any case,
// the common element here is that all 3 arrays need to start at the *end* and
// then work towards the front.
auto a1 = array_one.rbegin();
auto a2 = array_two.rbegin();
auto a3 = array_three.rbegin();
// Even though they might have different numbers of digits, we need to keep
// iterating as long as there is at least one array left with digits remaining.
while (a1 != array_one.rend() || a2 != array_two.rend()) {
int d1 =0, d2 = 0;
// First get a digit from the first array, or 0 if this number has no more
// digits. Move its pointer to the left, setting it to nullptr if it has no more
// digits.
if (a1 != array_one.rend()) {
d1 = *a1;
++a1;
}
// Then do the same for the second array.
if (a2 != array_two.rend()) {
d2 = *a2;
++a2;
}
// Add together the current digits, plus any existing carry (which has already been written
// to this position in the output by the previous step). Note that we use += since we need
// to factor in any carry which was already written here by an earlier step.
*a3 += d1 + d2;
// The new carry is the result of dividing the sum by 10 and throwing away the remainder.
// Write it straight into the next position.
*(a3+1) = *a3 / 1000000000;
// While the single-digit value for the output array is the modulus.
*a3 %= 1000000000;
// Move to the next digit in the output. Again, the carry has already been written here.
++a3;
}
