I guess I’ve found a slightly better solution for problem 5.2. Here’s the approach: starting from the end of the array iterate until a digit different from 9 is found then add 1 to this digit. Replace every digit equal to 9 with 0. If the end of the array is reached and no digit different from 9 is found then insert 1 at the top of the array.
auto increment( vector<int>& num) {
int i = num.size()-1;
for(; i>=0 && num[i] == 9; --i )
num[i] = 0;
if(i < 0)
num.insert(begin(num),1);
else ++num[i];
}
Complexity
Time: O(n)
Space: O(1)