Solution For Plus One

Problem:

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:
Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123.

Example 2:
Input: digits = [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321.

Example 3:
Input: digits = [0] Output: [1]

Approach:

We start from the last element in the given array and from there we check if adding 1 to the current element will result in a carry. If it does, we set the current element to 0 and move to the previous element, and repeat the process. If we reach the first element and it results in a carry, we add an extra element with 1 as its value, and that becomes the new most significant digit.

Algorithm:

1. Initialize a variable carry to 1
2. Loop from last index of the array to first index:
   a. Add the current digit to carry.
   b. If carry is equal to 10, then set carry to 1 and set current digit to 0
   else set carry to 0 and break from loop
3. If carry is still 1, create a new array of length n+1, where n is the length of the input array.
   Set the first element in the new array to 1 and copy the remaining elements from the input array to the new array starting from 2nd position.
   Else, copy the modified input array to a new array and return it.

Solution:

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

    for(int i=n-1; i>=0; i--) {
        int sum = digits[i]+carry;
        if(sum == 10) {
            carry = 1;
            digits[i] = 0;
        }
        else {
            carry = 0;
            digits[i] = sum;
            break;
        }
    }

    if(carry == 1) {
        int[] result = new int[n+1];
        result[0] = 1;
        for(int i=1; i<result.length; i++) {
            result[i] = digits[i-1];
        }
        return result;
    }
    else {
        return digits;
    }
}

}

Time Complexity: O(n), where n is the length of the input array.

Space Complexity: O(n), where n is the length of the input array, in case an extra element needs to be added to the array.

Step by Step Implementation For Plus One

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

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        #convert list to int
        num = int("".join(map(str, digits)))
        #add 1 to int
        num += 1
        #convert back to list
        return list(map(int, str(num)))

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    // We start from the back of the array
    // and keep track of the carry
    let carry = 1;
    for (let i = digits.length - 1; i >= 0; i--) {
        // Add the carry to the current digit
        let sum = digits[i] + carry;
        // Update the current digit with the ones digit
        digits[i] = sum % 10;
        // Update the carry
        carry = Math.floor(sum / 10);
    }
    // If there is a carry left over,
    // we need to add a new digit to the front of the array
    if (carry === 1) {
        digits.unshift(1);
    }
    return digits;
};

class Solution {
public:
    vector plusOne(vector& digits) {
        int n = digits.size();
        for(int i=n-1; i>=0; i--) {
            if(digits[i] == 9) {
                digits[i] = 0;
            }
            else {
                digits[i]++;
                return digits;
            }
        }
        // if all digits are 9, add 1 to the front of the vector
        digits[0] = 1;
        digits.push_back(0);
        return digits;
    }
};

public class Solution {
    public int[] PlusOne(int[] digits) {
        
        //edge case when the input is 99999
        if(digits.All(x => x == 9))
        {
            int[] result = new int[digits.Length+1];
            result[0] = 1;
            return result;
        }
        
        //plus one to the last digit
        digits[digits.Length-1]++;
        
        //if the last digit is now 10, we need to carry over
        for(int i = digits.Length-1; i > 0 && digits[i] == 10; i--)
        {
            digits[i] = 0;
            digits[i-1]++;
        }
        
        //if the first digit is now 10, we need to create a new array with length+1 and set first digit to 1
        if(digits[0] == 10)
        {
            digits[0] = 0;
            int[] result = new int[digits.Length+1];
            result[0] = 1;
            return result;
        }
        
        return digits;
    }
}