Welcome Reader!
We hope that you are doing great with Arrays so far. In the last blog, we discussed the problem of Moving Zeroes efficiently in an array. In this article, we will discuss the next problem based on “Arrays” i.e. “Plus One.” Before you move any further, it is advised that you give this problem a fair try. Let’s jump to the problem.
Important Link: Problem Link
Problem Statement
You are given a large integer represented as an integer array of digits, where each digit [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 0s.
Increment the large integer by one and return the resulting array of digits.
For example:
Sample Input -> [1,2,3]
Sample Output -> [1,2,4]
Sample Input -> [9,9,9]
Sample Output -> [1,0,0,0]
Approach
Traverse the array backward.
Check every element if it is 9 or beyond 9.
If the element is beyond 9, just increment the array's last element and break the loop.
If the element is 9, then replace the element with 0 and decrement the loop pointer by 1.
At last, check if the first element of the array is 0, then create a new array and place 1 on the 0th element of the new array.
Let's take an example -:
Let’s take an example where input is,
[9,9,9,9]
Place a pointer i on the last element of the array and traverse it backward.
If the element is 9, replace the element with 0 and decrement i by 1.
If the element is 9, again replace the element by 0 and decrement i by 1.
If the element is 9, again replace the element by 0 and decrement i by 1.
If the element is 9, again replace the element by 0 and decrement i by 1.
Now, i is at the null position, and the first element of the array is 0. So, we will create a new array and place 1 at the 0th index of the new array.
Let’s try to code this!
1.) Traverse the array from backward.
2.) Check if the element is 9 or not; if the element is not equal to 9, then just increment the last element of the array and break the loop and if the element is equal to 9, replace the element with 0.
3.) After the whole array is traversed, check if the first element of the array is 0 or not, if it is 0 then create a new array and place 1 on the 0th index of the new array.
Complexity Analysis
Time Complexity: O(N)
Where N = length of the input string. As we are traversing every array element for one time, the time complexity is O(N).
Space Complexity: O(N+1)
As we have created extra space in the worst case, the space complexity is O(N+1).
Complete Code:
We hope that this article was helpful. You can contact us via our website. Doubts, suggestions, and feedback are always welcomed. Keep practicing more and more problems daily. Meditate enough on each step of each problem.
“Don’t let the fear of losing be greater than the excitement of winning.”
-Robert Kiyosaki
All the best for an exciting future!
Happy Coding!
Contributed by: Parth Mathur
Regards,
The Daily Code Team.