DEV Community

loading...

LeetCode - Plus One

Alkesh Ghorpade
Ruby on Rails and Golang consultant
Originally published at alkeshghorpade.me ・3 min read

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/plus-one

Example 1:

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

Example 1:

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

Example 1:

Input: digits = [0]
Output: [1]
Enter fullscreen mode Exit fullscreen mode

Constraints:

- <= digits.length <= 100
- 0 <= digits[i] <= 9
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute Force approach

The basic approach that comes to our mind is converting the array into
number, increment it by 1, and then return the result in array form.

But for a very large array that cannot fit into a given data
type this approach can fail.

Incrementing from right to left

We can use the below algorithm to solve this problem:

- start from the last index of the array and process each digit till the first index.

- if the current digit is smaller than 9, add one to the current digit,
and return the array else assign zero to the current digit.

- if the first element is 9, then it means all the digits are 9.
  - increase the array size by 1, and set the first digit as 1.

- return array
Enter fullscreen mode Exit fullscreen mode
C++ solution
class Solution {
public:
    vector<int> plusOne(vector<int> &digits)
    {
        int i, size = digits.size(), carry = 1;

        for (i = size - 1; i >= 0 && carry != 0; i--){
            carry += digits[i];
            digits[i] = carry % 10;
            carry = carry / 10;
        }

        if( carry != 0 ){
            digits.emplace(digits.begin(), 1);
        }

        return digits;
    }
};
Enter fullscreen mode Exit fullscreen mode
Golang solution
func plusOne(digits []int) []int {
    carry := 1

    for i:= len(digits) - 1; i >= 0; i-- {
        digits[i] += carry

        if digits[i] < 10 {
            return digits
        } else {
            digits[i] = 0
            carry = 1
        }
    }

    if carry != 0 {
        return append([]int{1}, digits...)
    } else {
        return digits
    }
}
Enter fullscreen mode Exit fullscreen mode
Javascript solution
var plusOne = function(digits) {
    for(let i = digits.length - 1; i >= 0; i--) {
        digits[i]++;

        if( digits[i] > 9 ){
            digits[i] = 0;
        } else{
            return digits;
        }
    }

    digits.unshift(1);
    return digits;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

Input: digits = [8, 9, 9, 9]

Step 1: size = digits.size()
             = 4

        carry = 1

Step 2: i = size - 1
          = 4 - 1
          = 3

        i >= 0 && carry != 0
        3 >= 0 && 1 != 0
        true

        carry += digits[i]
              += digits[3]
              += 9

        carry = 10

        digits[3] = 10 % 10;
                  = 0

        carry = 10 / 10
              = 1

        i--
        i = 2

Step 3: i >= 0 && carry != 0
        2 >= 0 && 1 != 0
        true

        carry += digits[i]
              += digits[2]
              += 9

        carry = 10

        digits[2] = 10 % 10;
                  = 0

        carry = 10 / 10
              = 1

        i--
        i = 1

Step 4: i >= 0 && carry != 0
        1 >= 0 && 1 != 0
        true

        carry += digits[i]
              += digits[1]
              += 9

        carry = 10

        digits[1] = 10 % 10;
                  = 0

        carry = 10 / 10
              = 1

        i--
        i = 0

Step 4: i >= 0 && carry != 0
        0 >= 0 && 1 != 0
        true

        carry += digits[i]
              += digits[0]
              += 8

        carry = 9

        digits[1] = 9 % 10;
                  = 9

        carry = 9 / 10
              = 0

        i--
        i = -1

Step 5: carry != 0
        0 != 0
        false

Step 6: return digits

So the answer is [9, 0, 0, 0].
Enter fullscreen mode Exit fullscreen mode

Discussion (0)