Plus One LeetCode

This problem tests the understanding of array manipulation and basic arithmetic operations. It involves dealing with an integer array representing a large integer to which we have to add $1$ . The main goal here is to understand array operations because they are a necessary skill in problem-solving. Solving this problem will enhance your ability to traverse arrays, handle carry operations, and manage edge cases, such as when the integer has trailing $9$ ’s.

Problem statement

Given an integer array called nums that represents a large integer; our task is to increment this number and return the resulting integer array. Each element in the nums array corresponds to a digit of the integer where digits are ordered from most significant to least significant in left-to-right order.

Note: The given large integer does not have any leading $0$ ’s.

Constraints:

$1\leq$ nums.length $\leq 100$
$0\leq$ nums[i] $\leq 9$

Let’s take a look at a few examples to get a better understanding of the problem statement:

Solution

To solve the given problem, we will traverse the array from the end to the beginning. We start by moving along the nums array from the last digit. For each element, we check if it is a $9$ . If it is, we set it to $0$ and move to the next significant digit. If we encounter a digit that is not $9$ , we simply increment this digit by $1$ and return the array, as no further processing is required. If we traverse all the digits and all of them are $9$ ’s, they will all be set to $0$ . In this case, we need to handle the special case by appending the digit $1$ at the beginning of the array.

Let’s look at the algorithm:

Traverse the nums array from the last element toward the first.
If there are $9$ ’s at the end of the array, change them to $0$ ’s.
Upon encountering a digit that is not $9$ , increment it by $1$ and return the array, as no further steps are needed.
If all digits are $9$ ’s, they will now be $0$ ’s. In this scenario, we prepend the digit $1$ to the array and return the result.

Let’s look at the following illustration to get a better understanding of the solution:

def plus_one(nums):
	n = len(nums) - 1
	# Traversing the array from end to start
	for i in range(n, -1, -1):
		# If the element of the nums array is 9, change it to 0
		if nums[i] == 9:
			nums[i] = 0
		# Otherwise, increment 1 and return the result
		else:
			nums[i] += 1
			return nums
	# Add 1 to the start of the array if all digits were 9
	return [1] + nums
# Driver code
def main():
	nums = [[1, 0, 5], [9, 9], [1, 9, 3, 2, 1], [6, 8], [1, 7, 6, 9]]
	for i in range(len(nums)):
		print(i+1, '.', '\tGiven array: ', nums[i], sep='')
		result = plus_one(nums[i])
		print('\n\tThe result: ', result)
		print('-' * 100)
if __name__ == '__main__':
	main()

Plus One

After discussing the solution to the given problem, we will now discuss its complexity analysis.

Time complexity

The time complexity of the solution is $O(n)$ where $n$ is the length of nums array.

Space complexity

The space complexity is $O(n)$ even though the operations are done in-place. In the worst case, if all elements of the array are $9$ , we will need intermediate space to store the result, which will have $O(n+1)$ elements. Therefore, the overall space complexity is $O(n)$ .

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Plus One LeetCode

Problem statement

Knowledge test

Solution

Time complexity

Space complexity