Last Updated: 7 Jan, 2021
Increase Number By 1
Easy
Asked in companies
You are given an array of integers NUM consisting of N elements. This array represents the digits of a number. Your task is to increase the number by 1, or we can say you have to add 1 to this number. The number will be positive, and digits are stored so that the most significant digit is at the starting of the array.
For example:
Let input array is [1,3,2,7] so basically, this array represents the number 1327, the output will be [1,3,2,8].
Note:
The input may have 0 at the starting of the array, e.g., [0,3,5,7] is a valid input, but the output can not have 0 before the most significant digit. So [0,3,5,8] will be a wrong answer, and the correct answer will be [3,5,8].
Input Format:
The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.
The first line of each test case contains a number N denoting the size of the array.
The second line contains N space-separated distinct integers denoting the array elements.
Output format:
For each test case, print the output array elements are separated by space.
The output of every test case will be printed in a separate line.
Note :
You don’t have to print anything. It has already been taken care of. Just implement the given function.
Constraints
1 <= T <=10^2
1 <= N <=10^4
0 <= NUM[i] <= 9
Where 'N' is the number of elements in array 'NUM' and 'NUM[i]' represents the ith digit of number 'NUM'.
Time limit: 1 second
Approaches
We can update values by making a recursive algorithm.
- We will make a helper function say SOLVE() which will receive two parameters vector of digits and index and it will return an integer which represents CARRY(a carry is a digit that is transferred from one column of digits to another column of more significant digits).
- So our base condition is when an index is equal to the size of the vector then we will return CARRY as 1 because we need to add 1 to the vector.
- At each step, we will make recursive calls to SOLVE().
- Now work we will do is add CARRY to the current index value and the new CARRY will be (value/10) and will update the value to (value%10) and the function will return the new CARRY.
- One more condition arises if we are at index 0 and after adding carry if value becomes greater than 9.Then we need to add a new element as 1 at the beginning of vector and value will become 0.
- The array that SOLVE() will return still has a problem that there may be zeroes before the most significant bit.
- So we have to remove all the zeros before the most significant bit.
- While ARR[i]==0 erase the digit.
- Now return the ARR.
As we have to start adding from the least significant digit so we have to start adding 1 from the end. Along with this, we will keep an integer variable CARRY initialized to 1. Now at each digit set digit to digit+CARRY then CARRY will be equal to (digit)/10 and the digit will become (digit)%10.
- Let’s say we have a given array ARR.
- Initialize an integer variable CARRY=1.
- Iterate over ARR[i] for each N-1 <= i <= 0 and do:
- ARR[i]=ARR[i]+CARRY
- CARRY = ARR[i]/10
- ARR[i]= ARR[i]%10
- If CARRY is greater than 0 add a new digit as 1 at the start of the array.
- Now we have to remove all the zeros before the most significant bit.
- While ARR[i]==0 erase the digit.
- Now return the ARR.