• To solve this problem, my idea is to simulate the process of manual calculation. Add one to the least significant digit, if carry occurs, add one to the second least significant digit, see whether carry occurs, and so on, until carry doesn't occur.

This algorithm runs in O(length of the number) time complexity and O(1) space complexity.

``````class Solution {
``````

public:
vector<int> plusOne(vector<int>& dig) {
int i;
int len=dig.size();
dig[len-1]++;//add one to the least significant digit
for(i=dig.size()-1;i>0;i--)//deal carry except the most significant digit
{
dig[i-1]+=dig[i]/10;
dig[i]%=10;
}

``````    if(dig.front()>=10)//deal carry at the most significant digit
{
dig[0]%=10;//change to one-digit number.
dig.insert(dig.begin(),1);//insert 1 to the front.
}

while(dig.front()==0)//deal with leading zeros.It seems there is no such case.
{
dig.erase(dig.begin());
}
return dig;
}
``````

};

• class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n,i,j;
n=digits.size();
i=n-1;
while(digits[i]==9)
i--;
digits[i]+=1;
for(j=i+1;j<=n-1;j++)
digits[j]=0;
return digits;
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.