Add One To Number

Posted: 12 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Given a non-negative number represented as an array of digits, you have to add 1 to the number, i.e, increment the given number by one.

The digits are stored such that the most significant digit is at the starting of the array and the least significant digit is at the end of the array.

For Example
If the given array is {1,5,2}, the returned array should be {1,5,3}.
Note
Input array can contain leading zeros, but the output array should not contain any leading zeros (even if the input array contains leading zeroes).
For Example: 
If the given array is {0,2}, the returned array should be {3}.
Input Format
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

The first line of each test case contains a positive integer N, which represents the number of digits in the given number/array.

The next line contains 'N' single space-separated positive integers representing the elements of the array.
Output Format
For each test case, print the final number.

Print the output of each test case in a separate line.
Note
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 10
1 <= N <= 5 * 10^4
0 <= Arr[i] <= 9

Where Arr[i] is the i-th digit in the number.
Approach 1

The basic idea is to reverse the given array to make addition easier. 

We will maintain a variable ‘carry’ initially; it will be ‘1’ as we have to add 1 to the given number.

Now we will call a recursive function to add 1 to reversed array.


Recursive state: addOneToNumberHelper(Arr, N, carry, idx)

In each recursive state, we increment the value of idx.
 

In each recursive state, we will do these steps:

  • Add carry to the current digit (D += carry)
  • Store the last digit of the number received after the above addition ( D % 10 ) in the current position
  • Update the carry  ( carry = D / 10 )
  • Move to next recursive state with the new carry, i.e, addOneToNumberHelper(Arr, N, carry, idx + 1)
     

When we reach the end of the array (base case), we will append carry at the end of the array(if carry is not equal to zero) and then return from the recursive function.

Try Problem