LeetCode – Plus One

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list.

For example:
Q1.
int[] nums = {1,2,3,4};
int[] result = plusOne(nums);
the digits are in the result array are {1,2,3,5};

 Q2.
int[] nums = [(9,9,9,9};
int[] result = plusOne(nums);
the digits are in the result array are {1,0,0,0,0};

So step1, we need to check the last digit is 9, if it is not 9, then plus one and return the int[]. If it is 9, then change the digit to 0, and check next digit in the loop.

Step 2. if the first digit alos is 9, then we need to create a bigger int[] result to contain the one more digit and assign 1 to result[0].

class Solution {
    public int[] plusOne(int[] digits) {
        for(int i=digits.length -1 ; i >= 0 ; i--){
            if(digits[i] < 9){
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }

        int[] result= new int[digits.length + 1];
        result[0]= 1;
        return result;
    }
}

Time complexity : O(n). Travel the digits array numbers.
Space complexity : O(n). create the result[].

Reference:
https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/559/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s