Add One To Number

Easy
0/40
Average time to solve is 10m
84 upvotes
Asked in companies
MicrosoftHewlett Packard EnterpriseAmerican Express

Problem statement

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}.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1
3
3
1 2 3
2
9 9
1
4
Sample Output 1
1 2 4
1 0 0
5
Explanation For Sample Input 1
In the 1st test case, the number is 123 after adding 1 number becomes 124, hence the output will be {1,2,4}.

In the 2nd test case, the number is 99 after adding 1 number becomes 100, hence the output will be {1,0,0}.

In the 3rd test case, the number is 4 after adding 1 number becomes 5, hence the output will be {5}.
Sample Input 2
3
4
2 4 6 8 
1
0
2
0 2
Sample Output 2
2 4 6 9
1
3
Hint

Can you solve this problem using recursion?

Approaches (2)
Recursive

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.

Time Complexity

O(N), Where ‘N’ is the number of digits in the given number.
 

Reversing the array takes O(N) time and we traverse the given array only once, so the time complexity is O(N+N+N)=O(N).

Space Complexity

O(1)
 

Constant additional space is required.

Code Solution
(100% EXP penalty)
Add One To Number
Full screen
Console