Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

Given a non-negative integer represented by a non-empty array of integers, add one to that number.

The highest digit is stored at the beginning of an array, where each element stores only a single digit.

You can assume that this integer does not start with zero, except for the integer 0.

The sample

Input: digits = [1,2,3] output: [1,2,4] explanation: input array represents the number 123. Input: digits = [4,3,2,1] output: [4,3,2,2] explanation: input array represents the number 4321. Input: digits = [0] output: [1]Copy the code

prompt

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

Their thinking

Adding one to an integer inevitably involves rounding. For integers with less than 9 units, you can simply add one to return the result.

There are two scenarios where the units digit equals 9:

  • Ten digits and above are less than9The number of
  • The ten digits and above are composed of numbers9composition

In the first case, we just need to go forward, round up to numbers less than 9, add one and return the result.

In the second case, you need to create an array with the first digit changed to 1 and the remaining digits defaulted to 0.

Code implementation

class Solution {
    public int[] plusOne(int[] digits) {
        int idx = digits.length - 1;
        // Add one to the units digit
        ++digits[idx];

        // Walk forward, carry bit by bit
        while(idx > 0 && digits[idx] == 10){
            digits[idx] = 0;
            ++digits[--idx];
        }

        // Determine whether the first element needs to be carried
        if(digits[0] = =10) {// Create an array with the length +1, change the first element and return the result
            int[] ans = new int[digits.length + 1];
            ans[0] = 1;
            return ans;
        }

        returndigits; }}Copy the code

Complexity analysis

  • Time complexity: O(N)O(N)O(N)
  • Space complexity: O(1)O(1)O(1)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/pl…