# Plus One
**Difficulty:** EASY
[External](https://leetcode.com/problems/plus-one)
Canonical: https://scaleengineer.com/dsa/problems/plus-one
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Intuit](https://scaleengineer.com/companies/intuit), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Yahoo](https://scaleengineer.com/companies/yahoo), [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
You are given a **large integer** represented as an integer array `digits`, where each `digits[i]` is the `ith` digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading `0`'s.

Increment the large integer by one and return _the resulting array of digits_.

**Example 1:**

**Input:** digits = [1,2,3]
**Output:** [1,2,4]
**Explanation:** The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

**Example 2:**

**Input:** digits = [4,3,2,1]
**Output:** [4,3,2,2]
**Explanation:** The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

**Example 3:**

**Input:** digits = [9]
**Output:** [1,0]
**Explanation:** The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

**Constraints:**

* `1 <= digits.length <= 100`
* `0 <= digits[i] <= 9`
* `digits` does not contain any leading `0`'s.

# Approaches
## Using BigInteger
This approach converts the array of digits into a data type that can handle arbitrarily large integers, such as Java's `BigInteger`. The process involves first building a string from the digit array, parsing it into a `BigInteger`, performing the addition, and then converting the result back into an array of digits. While straightforward, it's not the most performant solution.
**Time:** O(N) · **Space:** O(N)
**Pros:** The logic is simple to understand and write, as it offloads the complex arithmetic to a built-in library.; It correctly handles all edge cases, including very large numbers and the case where the number of digits increases (e.g., 999 + 1).
**Cons:** Significantly less efficient due to the overhead of creating multiple objects (`StringBuilder`, `BigInteger`, `String`) and performing conversions between data types.; This approach abstracts away the core arithmetic logic, which might not be what an interviewer is looking for when asking this type of question.
### Explanation
The core idea is to leverage a high-level library designed for arbitrary-precision arithmetic. Instead of manually handling the carry logic, we delegate the entire addition operation to the `BigInteger` class.

```java
import java.math.BigInteger;

class Solution {
    public int[] plusOne(int[] digits) {
        // 1. Convert array to a string representation.
        StringBuilder sb = new StringBuilder();
        for (int digit : digits) {
            sb.append(digit);
        }
        
        // 2. Create a BigInteger from the string.
        BigInteger number = new BigInteger(sb.toString());
        
        // 3. Add one.
        number = number.add(BigInteger.ONE);
        
        // 4. Convert the result back to a string.
        String resultStr = number.toString();
        
        // 5. Convert the string back to an integer array.
        int[] result = new int[resultStr.length()];
        for (int i = 0; i < resultStr.length(); i++) {
            result[i] = resultStr.charAt(i) - '0'; // Convert char to int
        }
        
        return result;
    }
}
```
### Algorithm
- Create a `StringBuilder` to hold the string representation of the integer.
- Iterate through the `digits` array and append each digit to the `StringBuilder`.
- Convert the `StringBuilder` to a `String` and then construct a `java.math.BigInteger` object.
- Use the `add()` method of `BigInteger` to add one to the number.
- Convert the resulting `BigInteger` back to a `String`.
- Create a new integer array with a size equal to the length of the result string.
- Iterate through the result string, convert each character back to an integer, and populate the new array.
- Return the new array.

## Schoolbook Addition Simulation
This optimal approach simulates the elementary school method of adding one to a number on paper. We start from the rightmost digit and move left. We add one to the last digit. If it's less than 10, we're done. If it becomes 10, we set it to 0 and carry a 1 to the next digit to the left. This process is repeated until we no longer have a carry or we've processed all digits.
**Time:** O(N) · **Space:** O(1) for average cases, O(N) for the worst case (input is all 9s)
**Pros:** Extremely efficient in both time and space.; Operates in-place for all cases except when the number of digits increases (e.g., 999 + 1).; Avoids overhead from string conversions and `BigInteger` object creation.
**Cons:** Requires special handling for the case where all digits are 9, which involves creating a new, larger array.
### Explanation
This method directly manipulates the input array to reflect the addition. It's highly efficient because it avoids any data type conversions and only iterates through the array once. Most cases (e.g., `[1,2,3]`) are resolved very quickly by just modifying the last digit. The only case that requires traversing the whole array is when the digits are all or mostly 9s.

```java
class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;

        // Iterate from the last digit to the first
        for (int i = n - 1; i >= 0; i--) {
            // Increment the current digit
            digits[i]++;

            // If the digit is now less than 10, there's no carry.
            // We can return the updated array immediately.
            if (digits[i] < 10) {
                return digits;
            }

            // Otherwise, the digit was 9, it became 10. Set it to 0
            // and the loop will continue to carry over the 1.
            digits[i] = 0;
        }

        // If the loop finishes, it means all digits were 9s.
        // We need to create a new array with an additional leading 1.
        // e.g., [9, 9, 9] -> [1, 0, 0, 0]
        int[] newNumber = new int[n + 1];
        newNumber[0] = 1;
        // The rest of the elements in newNumber are already 0 by default.

        return newNumber;
    }
}
```
### Algorithm
- Get the length of the `digits` array, `n`.
- Iterate through the array from right to left (from index `n-1` down to `0`).
- In each iteration, increment the current digit `digits[i]`.
- Check if the incremented digit is less than 10. If it is, there is no carry-over. We can immediately return the modified `digits` array.
- If the incremented digit is 10, it means we have a carry. Set the current digit to `0` and let the loop continue to the next digit to the left, which will then be incremented in the next iteration.
- If the loop completes, it means every digit was a 9, and we have a carry-over from the most significant digit. 
- In this special case, create a new array of size `n+1`. Set the first element of this new array to `1` (the carry-over). The remaining elements will default to `0`.
- Return this new array.

# Solutions
### Java

```java
class Solution {
public
  int[] plusOne(int[] digits) {
    int n = digits.length;
    for (int i = n - 1; i >= 0; --i) {
      ++digits[i];
      digits[i] %= 10;
      if (digits[i] != 0) {
        return digits;
      }
    }
    digits = new int[n + 1];
    digits[0] = 1;
    return digits;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} digits * @return {number[]} */ var plusOne = function (
  digits,
) {
  for (let i = digits.length - 1; i >= 0; --i) {
    ++digits[i];
    digits[i] %= 10;
    if (digits[i] != 0) {
      return digits;
    }
  }
  return [1, ...digits];
};

```

### CPP

```cpp
class Solution {
public:
  vector<int> plusOne(vector<int> &digits) {
    for (int i = digits.size() - 1; i >= 0; --i) {
      ++digits[i];
      digits[i] %= 10;
      if (digits[i] != 0)
        return digits;
    }
    digits.insert(digits.begin(), 1);
    return digits;
  }
};

```

### Python

```python
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]: n = len(digits) for i in range(n - 1, - 1, - 1): if digits[i] < 9: digits[i] += 1 return digits digits[i] = 0 return [1] + digits  # also ok: return [1] + [0]*n ############ class Solution ( object ): def plusOne ( self , digits ): """ :type digits: List[int] :rtype: List[int] """ carry = 1 for i in reversed ( range ( 0 , len ( digits ))): digit = ( digits [ i ] + carry ) % 10 carry = 1 if digit < digits [ i ] else 0 digits [ i ] = digit if carry == 1 : return [ 1 ] + digits return digits

```