Question

66. Plus One

中文文档

Description

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.

Solutions

Solution 1: Simulation

We start traversing from the last element of the array, add one to the current element, and then take the modulus by $10$. If the result is not $0$, it means that there is no carry for the current element, and we can directly return the array. Otherwise, the current element is $0$ and needs to be carried over. We continue to traverse the previous element and repeat the above operation. If we still haven't returned after traversing the array, it means that all elements in the array are $0$, and we need to insert a $1$ at the beginning of the array.

The time complexity is $O(n)$, where $n$ is the length of the array. Ignoring the space consumption of the answer, the space complexity is $O(1)$.

class Solution:
  def plusOne(self, digits: List[int]) -> List[int]:
    n = len(digits)
    for i in range(n - 1, -1, -1):
      digits[i] += 1
      digits[i] %= 10
      if digits[i] != 0:
        return digits
    return [1] + digits

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;
  }
}

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;
  }
};

func plusOne(digits []int) []int {
  n := len(digits)
  for i := n - 1; i >= 0; i-- {
    digits[i]++
    digits[i] %= 10
    if digits[i] != 0 {
      return digits
    }
  }
  return append([]int{1}, digits...)
}

function plusOne(digits: number[]): number[] {
  const n = digits.length;
  for (let i = n - 1; i >= 0; i--) {
    if (10 > ++digits[i]) {
      return digits;
    }
    digits[i] %= 10;
  }
  return [1, ...digits];
}

impl Solution {
  pub fn plus_one(mut digits: Vec<i32>) -> Vec<i32> {
    let n = digits.len();
    for i in (0..n).rev() {
      digits[i] += 1;
      if 10 > digits[i] {
        return digits;
      }
      digits[i] %= 10;
    }
    digits.insert(0, 1);
    digits
  }
}

/**
 * @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];
};