Last Updated: 12 Nov, 2020
Add One To Number
Easy
Asked in companies
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.
Approaches
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.
The problem can be solved by simply iterating the given array and doing the same steps as did in the recursive function.
Algorithm
- Reverse the given array and remove leading zeroes.
- Initialize a variable ‘carry’ to 1.
- Traverse the given array using a variable ‘i’
- Add carry to the current digit and store result in a variable ‘D’ (D = arr[i] + 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 )
In the end, if carry is not equal to zero, append carry to the end of the array.
The reverse of the array will be the desired output.
Similar problems