[toc]
Company Tags: Google, Amazon, Apple, Adobe, Microsoft, Facebook
This is one of the frequently asked questions in interviews by giant organizations like Google, Microsoft, and Facebook. Will you be able to solve it optimally if it showed up in your interview?
Problem Statement
Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer and return the output array. 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.
Note: You may assume the integer does not contain any leading zero, except the number 0 itself.
Constraints
◈ 1 <= digits.length <= 100
◈ 0 <= digits[i] <= 9
Examples
Let’s have a look at some examples to improve our understanding of this problem.
Example 1:
Input: nums = [1, 2, 3]
Output: [1, 2, 4]
Explanation: The array represents the integer 123. 123 + 1 = 124
Example 2:
Input: nums = [5, 6, 8, 5]
Output: [5, 6, 8, 6]
Explanation: The array represents the integer 5685. 5685 + 1 = 5686
Example 3:
Input: nums = [9]
Output: [1, 0]
Explanation: The array represents the integer 9. 9 + 1 = 10. But every element can have only one digit.
Example 4:
Input: nums = [0]
Output: [1]
Explanation: The array represents the integer 0. 0 + 1 = 1
Example 5:
Input: nums = [3, 9, 9]
Output: [4, 0, 0]
Explanation: The array represents the integer 399. 399 + 1 = 400.
Now that you have a clear picture of the problem let’s dive into the solutions.
Method 1: Using Extra Space
Approach: The idea of this approach is to reverse the given array and then work on it with the help of a carry variable. If the first digit is any number other than 9, you have to add one to it. Otherwise, add one to the first digit and iterate over the other digits in the number to check if all the digits in the array are 9. If all digits are 9, append one to the array and return the array after reversing it again. Let’s look at the algorithm to further understand this:
Algorithm
- First, store the reversed array in a new array, i.e.,
num, and initialize the value of thecarryvariable as0. - If the current number is equal to
9, then carry the value forward to the next element. Repeat this till you reach the last element of the array. - Else, add one to the current number.
- If the carry remains one, it implies that all the numbers in the array are
9. In this case, append1to the start of the array. - Return the array after re-reversing it.
Let’s implement the algorithm as a code:
def plus_one(num):
carry = 0
num = nums[::-1]
if num[0] == 9:
n = num[0] + 1
num[0] = n % 10
carry = 1
for i in range(1, len(num)):
n = num[i] + carry
num[i] = n % 10
carry = n // 10
else:
num[0] = num[0] + 1
if carry:
num.append(1)
return num[::-1]
Let’s run this code on our examples to check if it works:
# Example 1
nums = [1, 2, 3]
print(plus_one(nums))
# [1, 2, 4]
# Example 2
nums = [5, 6, 8, 5]
print(plus_one(nums))
# [5, 6, 8, 6]
# Example 3
nums = [9]
print(plus_one(nums))
# [1, 0]
# Example 4
nums = [0]
print(plus_one(nums))
# [1]
# Example 5
nums = [3, 9, 9]
print(plus_one(nums))
# [4, 0, 0]Yeah! It passed all the test cases.
Complexity Analysis
- Time Complexity: In this method, you have to traverse the list only once. Thus, the runtime complexity of this approach is O(n).
- Space Complexity: The space complexity of this method is O(n), as we have created a new array
numto store the elements of the original array in reverse order.
Discussion:
In this method, we have traversed the entire array in every case. Although we know that we only have to update the carry when the number is 9 else it remains 0. So, is there a possible solution where we can update the value in the original array itself without creating a whole new array? That will be a better solution as we can terminate the process when the digit becomes less than 9.
Method 2: Without Using Extra Space [Optimal Solution]
In the previous approach, we had to reverse the array before traversing it. This meant we needed an extra array to store the reversed elements. To avoid this, we can traverse the array from the end. This not only helps us to avoid the requirement of an extra array to store reversed elements but it is also more efficient in terms of time complexity as we don’t have to travel the whole array to update the last variable.
Approach:
- Start traversing the array from the end.
- If the current number in the array is smaller than 9, then add one to the current number and then return the array.
- If the current number is 9, assign zero to the current number and traverse to the next number.
- If at any point the number becomes less than 9 while traversing, we can return the array after adding 1.
- In case all the numbers in the array are 9, it means we have to increase the length of the array by one. Thus, assign zero in place of all the 9’s in the array and prepend the element/digit 1 to it.
To improve our understanding of the approach, let’s have a look at the following illustration:
Explanation: In the above example, the given array is [3,9,9]. As the last element is 9, we replaced every successive occurrence of 9 by 0. Finally, we added one to the value at the first index, i.e., 3+1=4.
Let’s have a look at another scenario where all the numbers in the given array/list are 9, i.e., the given array = [9,9,9].
Explanation: In the above example, since all the elements of the array are 9, we replace them with 0 and finally prepend 1 to the array.
Let’s have a look at the code:
def plus_one(nums):
n = len(nums)-1
while n>=0:
if nums[n]<9:
nums[n] = nums[n] + 1
return nums
nums[n] = 0
n = n - 1
return [1] + numsLet’s execute the test cases on this code to verify if this algorithm works:
# Example 1
nums = [1, 2, 3]
print(plus_one(nums))
# [1, 2, 4]
# Example 2
nums = [5, 6, 8, 5]
print(plus_one(nums))
# [5, 6, 8, 6]
# Example 3
nums = [9]
print(plus_one(nums))
# [1, 0]
# Example 4
nums = [0]
print(plus_one(nums))
# [1]
# Example 5
nums = [3, 9, 9]
print(plus_one(nums))
# [4, 0, 0]Hurrah! The code passed all the test cases successfully.
Complexity Analysis:
- Time Complexity: Since in the worst case scenario, we have to traverse the array once in this approach, the time complexity of this approach is O(n). Here,
nis the length of the array. - Space Complexity: If the array contains at least one digit that is smaller than 9, the space complexity of this method will be O(1). However, if all the digits are 9, the space complexity becomes O(n).
Method 3: Using Recursion
Another approach to solving this problem is to use recursion. Thus, in this method, within the base case, we have to check if the given array has only one element, i.e., whether it comprises a single number. If the array has more than one number then the recursive call comes into the picture. Within the recursive function, if the last number is equal to 9, then we call the recursive function again by passing the array with all its elements except the last element as an input to the function.
Let’s look at the following code to understand how to implement the concept explained above:
def plus_one(nums):
if len(nums) == 1:
if nums[0] == 9:
return [1,0]
else:
nums[0] = nums[0] + 1
return nums
else:
if nums[-1] == 9:
l = plus_one(nums[:-1])
l.append(0)
return l
else:
nums[-1] = nums[-1] + 1
return numsYet again, to check the validity of the above code let us execute the test cases upon the code:
# Example 1
nums = [1, 2, 3]
print(plus_one(nums))
# [1, 2, 4]
# Example 2
nums = [5, 6, 8, 5]
print(plus_one(nums))
# [5, 6, 8, 6]
# Example 3
nums = [9]
print(plus_one(nums))
# [1, 0]
# Example 4
nums = [0]
print(plus_one(nums))
# [1]
# Example 5
nums = [3, 9, 9]
print(plus_one(nums))
# [4, 0, 0]
It successfully passed all the test cases.
Complexity Analysis: The runtime complexity of this method remains the same, i.e., O(n).
Conclusion
I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.
Post Credits: Shubham Sayon and Rashi Agarwal
Recommended: Finxter Computer Science Academy
- Do you want to master the most popular Python IDE fast?
- This course will take you from beginner to expert in PyCharm in ~90 minutes.
- For any software developer, it is crucial to master the IDE well, to write, test and debug high-quality code with little effort.
