Plus One - Leet Code Solution
September 03, 2020
Problem Statement
Given a non-empty array of digits representing a non-negative integer, increment one to the integer.
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.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example
Input: digits = [1,2,3]
Output: [1,2,4]
Solution
It has very simple solution, just by iterating array from the end. And, keeping track of carry.
A simple complexity here is that result can be bigger than original array if we got a carry for the last sum.
Code
public int[] plusOne(int[] digits) {
int l = digits.length;
//initializing carry with the number we want to add for first time.
int carry = 1;
for (int i=l-1; i>=0; i--) {
digits[i] = digits[i] + carry;
carry = digits[i]/10;
digits[i] = digits[i]%10;
}
// copy result to another array
int targetSize = carry == 1 ? l+1 : l;
int[] res = new int[targetSize];
int i=0;
if (carry == 1) {
res[0] = carry;
i = 1;
}
for (; i<targetSize; i++) {
res[i] = digits[i-carry];
}
return res;
}
Complexity
Its O(n)
Similar Posts
Maximum Length of Subarray With Positive Product - Leet Code Solution
Problem Statement Maximum Length of Subarray With Positive Product. Given an…
Calculate Max Profit - Buy and Sell Stocks Multiple Times - Leet Code Solution
Problem Statement Say you have an array prices for which the ith element is the…
Longest Common Prefix - Leet Code Solution
Problem Statement Write a function to find the longest common prefix string…
Three Sum Closest - Leet Code Solution
Problem Statement Given an array nums of n integers and an integer target, find…
Four Sum - Leet Code Solution
Problem Statement Given an array nums of n integers and an integer target, are…
Latest Posts
System Design Interview Vocabulary Notes
In this post, we will see some of the frequently used concepts/vocabulary in…
Coding Interview - Facebook System Design Interview Types
System design interview is pretty common these days, specially if you are having…
Find the maximum sum of any continuous subarray of size K
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting - Build System Order Example
Graph Topological Sorting This is a well known problem in graph world…
Binary Tree - Level Order Traversal
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Four Sum - Leet Code Solution
Problem Statement Given an array nums of n integers and an integer target, are…