# Add to Array-Form of Integer
**Difficulty:** EASY
[External](https://leetcode.com/problems/add-to-array-form-of-integer)
Canonical: https://scaleengineer.com/dsa/problems/add-to-array-form-of-integer
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Avito](https://scaleengineer.com/companies/avito), [ByteDance](https://scaleengineer.com/companies/bytedance), [Zoho](https://scaleengineer.com/companies/zoho)
---
## Problem
The **array-form** of an integer `num` is an array representing its digits in left to right order.

* For example, for `num = 1321`, the array form is `[1,3,2,1]`.

Given `num`, the **array-form** of an integer, and an integer `k`, return _the **array-form** of the integer_ `num + k`.

**Example 1:**

**Input:** num = [1,2,0,0], k = 34
**Output:** [1,2,3,4]
**Explanation:** 1200 + 34 = 1234

**Example 2:**

**Input:** num = [2,7,4], k = 181
**Output:** [4,5,5]
**Explanation:** 274 + 181 = 455

**Example 3:**

**Input:** num = [2,1,5], k = 806
**Output:** [1,0,2,1]
**Explanation:** 215 + 806 = 1021

**Constraints:**

* `1 <= num.length <= 104`
* `0 <= num[i] <= 9`
* `num` does not contain any leading zeros except for the zero itself.
* `1 <= k <= 104`

# Approaches
## BigInteger Conversion
This approach converts the input array `num` into a `BigInteger` object, adds `k` to it, and then converts the resulting `BigInteger` back into an array of digits. It leverages Java's built-in library for handling arbitrarily large integers.
**Time:** O(N + M), where N is the length of `num` and M is the number of digits in the sum. This is because converting the array to a string takes O(N), `BigInteger` operations take time proportional to the number of digits, and converting the final string to a list takes O(M). Since M is approximately max(N, log10(k)), the complexity is O(N). · **Space:** O(N + M), for storing the string representations and the final result list, where N is the length of `num` and M is the number of digits in the sum. This simplifies to O(N).
**Pros:** Simple to implement if you are familiar with the `BigInteger` class.; Reduces the chance of implementation errors in the arithmetic logic by using a well-tested library.
**Cons:** Less efficient due to the overhead of creating multiple intermediate objects (StringBuilder, BigInteger, String).; Involves multiple data type conversions which can be slow.; May not be what an interviewer is looking for, as it abstracts away the core addition logic.
### Explanation
The core idea is to delegate the complex arithmetic of large numbers to the `java.math.BigInteger` class, which is designed for this purpose.

**Algorithm Steps:**
1.  Convert the `num` array into its string representation. For example, `[1,2,0,0]` becomes `"1200"`.
2.  Create a `BigInteger` instance from this string.
3.  Create another `BigInteger` instance from the integer `k`.
4.  Use the `add()` method of `BigInteger` to compute the sum.
5.  Convert the resulting `BigInteger` sum back to a string.
6.  Iterate through the characters of the result string, convert each character to its numeric value, and add it to a list.
7.  Return the final list of digits.

```java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        // 1. Convert num array to a string
        StringBuilder sb = new StringBuilder();
        for (int digit : num) {
            sb.append(digit);
        }
        String numStr = sb.toString();

        // 2. Create BigInteger objects and add them
        BigInteger numBigInt = new BigInteger(numStr);
        BigInteger kBigInt = BigInteger.valueOf(k);
        BigInteger sumBigInt = numBigInt.add(kBigInt);

        // 3. Convert the sum back to a string
        String sumStr = sumBigInt.toString();

        // 4. Convert the sum string to a list of integers
        List<Integer> result = new ArrayList<>();
        for (char c : sumStr.toCharArray()) {
            result.add(c - '0');
        }

        return result;
    }
}
```
### Algorithm
- Convert the `num` array to a string.
- Create a `BigInteger` from the string representation of `num`.
- Create a `BigInteger` from the integer `k`.
- Add the two `BigInteger` objects.
- Convert the resulting `BigInteger` sum back to a string.
- Create a new list and populate it with the digits from the sum string.
- Return the list.

## Schoolbook Addition
This approach simulates the manual, pencil-and-paper method of adding two numbers. It processes the numbers from right to left (least significant digit to most significant), keeping track of a carry value at each step.
**Time:** O(max(N, log10(k))), where N is the length of the `num` array. The loop runs once for each digit of the larger number. This is effectively O(N) given the constraints. · **Space:** O(max(N, log10(k))) for the result list. If the output list is not considered auxiliary space, the space complexity is O(1).
**Pros:** Highly efficient with optimal time and space complexity.; Avoids intermediate data structures like strings or `BigInteger` objects, reducing overhead.; Demonstrates a fundamental understanding of arithmetic operations.
**Cons:** Slightly more complex to implement correctly compared to the `BigInteger` approach.
### Explanation
This is the most efficient way to solve the problem as it performs the addition in a single pass without any expensive type conversions or large object allocations. The algorithm iterates through the `num` array from right to left, adding the digits of `k` and any carry from the previous step. The integer `k` itself is used to carry over the sum to the next higher-order digit.

**Algorithm Steps:**
1.  Initialize a `LinkedList` to store the result digits. A `LinkedList` is chosen for its efficient O(1) `addFirst` operation, which avoids a final reversal step.
2.  Start a loop that continues as long as there are digits left in `num` to process or `k` (which holds the carry and remaining part of the number to be added) is greater than 0.
3.  In each iteration, if there's a digit in `num` at the current position, add it to `k`.
4.  The current digit for the result is `k % 10`.
5.  The new carry is `k / 10`. We update `k` to this value for the next iteration.
6.  Prepend the current digit (`k % 10`) to the result list.
7.  Move to the next digit in `num` by decrementing the pointer.
8.  After the loop, the `LinkedList` contains the digits of the sum in the correct order. Return it.

```java
import java.util.LinkedList;
import java.util.List;

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        LinkedList<Integer> result = new LinkedList<>();
        int i = num.length - 1;

        while (i >= 0 || k > 0) {
            // Add the current digit of num if it exists
            if (i >= 0) {
                k += num[i];
                i--;
            }
            
            // The current digit of the sum is k % 10
            result.addFirst(k % 10);
            
            // The carry is k / 10
            k /= 10;
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize an empty `LinkedList` for the result.
- Initialize a pointer `i` to the last index of `num`.
- Loop as long as `i` is valid (`>= 0`) or `k > 0`.
- Inside the loop, if `i` is valid, add `num[i]` to `k`.
- Add the last digit of the current sum (`k % 10`) to the front of the result list.
- Update `k` to be the carry (`k / 10`).
- Decrement `i`.
- Return the result list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> addToArrayForm(int[] num, int k) {
    int i = num.length - 1, carry = 0;
    LinkedList<Integer> ans = new LinkedList<>();
    while (i >= 0 || k > 0 || carry > 0) {
      carry += (i < 0 ? 0 : num[i--]) + k % 10;
      ans.addFirst(carry % 10);
      carry /= 10;
      k /= 10;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> addToArrayForm(vector<int> &num, int k) {
    int i = num.size() - 1, carry = 0;
    vector<int> ans;
    for (; i >= 0 || k || carry; --i) {
      carry += (i < 0 ? 0 : num[i]) + k % 10;
      ans.push_back(carry % 10);
      carry /= 10;
      k /= 10;
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]: i, carry = len(num) - 1, 0 ans = [] while i >= 0 or k or carry: carry += (0 if i < 0 else num[i]) + (k % 10) carry, v = divmod(carry, 10) ans . append(v) k //= 10 i -= 1 return ans[:: - 1]

```