Problem 5.2 - Increment an arbitrary precision integer - Alternative Solution

#1

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)

0 Likes

#2

Hi @bytecrunch,

Many thanks for your alternative solution, and it is definitely a different implementation over the same idea. One difference between your approach with the one in the book is that your might insert a 0 in the beginning which is an expensive
but one time operation. However, yours are doing less work during the loop.

It is always good to see people providing different implementation of the problem, and good job for sure!

0 Likes