Posted: 12 Nov, 2020
Difficulty: Easy

## PROBLEM STATEMENT

#### 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.