Plus One Leetcode Solution

Difficulty Level Easy
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutions

Problem statement

In the problem ” Plus One”  we are given an array where each element in the array represents a digit of a number. The complete array represents a number. The zeroth index represents the MSB of the number.  We can assume that there is no leading zero in the number.

Our task is to plus one the given number and then return the result in the form of an array.

Example

digits =[4,3,2,1]
[4,3,2,2]

Explanation: As in the given example, the array represents 4321 and 4321+1 becomes 4322. So we returned  4322.

Approach for Plus One Leetcode Solution

The first idea that comes into everybody’s mind is to convert the given array into a number, perform an addition operation, and then return the result in the form of an array.

But this idea will fail for a large size array as it would not fit into any data type.

So, we need to process each digit one by one.

1. Start from the LSB and then process each digit till MSB.
2. If the current digit is smaller than 9 then add one to the current digit and return the array else assign zero to the current digit.
3. If the last element is processed and it was also equal to 9, it means that all the digits were 9. So, we will increase the size of the array by one and assign 1 to the MSB.
4. Return the array
Smallest Good Base

C++ code for Plus One

#include <bits/stdc++.h>
using namespace std;
vector<int> plusOne(vector<int>& digits) {
int n=digits.size();
for(int i=n-1;i>=0;i--)
{
if(digits[i]<9)
{digits[i]++ ; return digits;}
else
digits[i]=0;
}
vector<int>newnumber(n+1,0);
newnumber=1;
return newnumber;
}
int main()
{
vector<int> arr = {4,3,2,1};
vector<int>ans= plusOne(arr);
for(int i=0;i<arr.size();i++)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
[4,3,2,2]

Java code for Plus One

import java.util.Arrays;
public class Tutorialcup {
public static int[] plusOne(int[] digits) {

int n = digits.length;
for(int i=n-1; i>=0; i--) {
if(digits[i] < 9) {
digits[i]++; return digits;
}
digits[i] = 0;
}

int[] newNumber = new int [n+1];
newNumber = 1;
return newNumber;
}
public static void main(String[] args) {
int [] arr = {4,3,2,1};
int[]ans=plusOne(arr);
System.out.println(Arrays.toString(ans));
}
}
[4,3,2,2]

Complexity Analysis of Plus One Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the digits array only once. Here n is the length of the digit array.

Space complexity

The space complexity of the above code is O(1)  in case the array contains at least one digit smaller than 9, otherwise O(n).

References