Algorithms Roadmap

Problem Statement

Plus One - 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.

Approach

This question brought back memories of how I used to do additions when I was a kid. It’s a fairly straightforward problem, we can perform an in-place addition by adding 1 to the last index. If the result is more than 10, we maintain a carry and add it to the previous cell. This process is continued till the carry is 0.

One edge case to consider is when the input consists of all nines. In this scenario, the array size will increase by one, so in-place modification won’t work. We’ll need to initialise a new array to accommodate the new digit. Either, check for this case in the beginning or at the end.

Code Implementation

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

                //carry will be 1 here, so initialise a new array 
                int[] nums = new int[digits.length+1];
                nums[0] = 1;
                return nums;
            }
        }
   

Since, this problem was easy and I was able to solve it quickly, I’m going to make it challenging by implementing a plusK algorithm. In this approach, instead of simply adding 1, k will be added to the input digits. I’ll be using this to solve the original plusOne problem. To implement this, I'll be using ArrayList instead of performing an in-place update.

Code Implementation

  
        public static int[] plusK(int[] digits, int k) {
            List result = new ArrayList<>();
            int carry = k;
            for(int i=digits.length-1;i>=0;i--){
                carry = digits[i] + carry;
                result.add(0,  carry%10);
                carry = carry/10;
            }

            while(carry>0){
                result.add(0,  carry%10);
                carry = carry/10;
            }
            return result.stream().mapToInt(Integer::intValue).toArray();
        }

        public int[] plusOne(int[] digits) {
            return plusK(digits, 1);
        }