Increment arbitrary precision number

Increment Arbitrary  precision number

 

Problem Statement

Write a program that takes an array of digits encoding a decimal number D and updates the array to represent the number D+1. 

Problem Solving

• Straight forward I can think of doing arithmetic as taught in school. 
• Add 1 to the last digit if the digit becomes more than 9 then carry repeat the process on the next digit. 
• Since we always increment the digit by 1 therefore we only need to check for digit 9.
• So we iterate the array in reverse order if the digit is non -9 then increment it by one and return else set it to 0 and keep iterating till end.
• If we reach the end that means that all digits were 9 hence we need to insert a 1 in the beginning. 
• Find Code here

 Learning 

• Due to one stupid mistake I learnt quite a few things here.   
• First since the google C++ style guide mentions that always take pointer as arguments if we wish to modify it. That makes the caller confident about what objects will be modified. 
• However to work with it we try not to use pointer in the callee function instead we cast it to a normal object. However if we try to write something like A a = *b. then a is a copy of value b. which is not what we want instead always do A &a = *b then a is a reference to the pointer value.
• This also gave me a better understanding about references and their uses in c++. 
• References are not variables that is they do not have any memory of there own they are just compiler syntactic sugar. 
• Overall the problem was naive. 
• Time complexity is linear while space is constant.