Increment An Integer Represented As An Array ("Plus One" on LeetCode)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given an array that represents an integer digit by digit, perform an increment by 1 operation on it.
Examples:
1
Input
[ 1, 2, 9 ]
Output
[ 1, 3, 0 ]
2
Input
[ 9, 9, 9, 9 ]
Output
[ 1, 0, 0, 0, 0 ]
Approach 1 (Brute Force)
Convert the array to an integer.
Increment the integer.
Re-codify the integer as an array or just place it back into the original array digit by digit.
When we have an array of a certain size this will fail because of integer overflow on the initial conversion (array to integer).
Whenever we get an integer represented as an array or an integer as a string we are never going to go back to its original form.
The point of the question is for you to do the operation within the confines of the question.
Approach 2 (Increment Within The Array)
We can just simulate the incrementing by 1 starting at the last element.
If we increment and that element becomes 10 we need to continue incrementing to the left until we reach the start of the array.
Edge Case: We then check the first element, if it is 10 then we need to expand the array by 1 and set the first element to 1.
Complexities
Time: O( n )
We may potentially have to perform n increments followed by lengthening the array to add a 1 in the most significant digit
All of these operations run in linear time.
Space: O( 1 )
We operate within the original array given and do not create additional space.
In the case where we need to expand the array by 1 element at the front we will be creating a new array and copy the elements over but this is an edge case and is an internal API operation so isn't often counted.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 6.2 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.