Increase Number By 1

Easy
0/40
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in companies
HashedInD.E.Shaw

Problem statement

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

Sample input 1:

4
4
0 0 9 9
3
1 2 9
7
1 1 1 1 1 1 1
5
9 9 9 9 9

Sample output 1:

1 0 0 
1 3 0
1 1 1 1 1 1 2
1 0 0 0 0 0

Sample input 2:

4
5
1 1 2 2 1
4
5 6 7 9
7
1 2 3 1 2 3 1
1
9

Sample output 2:

1 1 2 2 2
5 6 8 0
1 2 3 1 2 3 2
1 0
Hint

After the addition of 1, the value of each digit is dependent on the value of the digit just right to it.

Approaches (2)
Recursive Approach

We can update values by making a recursive algorithm.

 

  1. 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).
  2. 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.
  3. At each step, we will make recursive calls to SOLVE().
  4. 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.
  5. 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.
  6. The array that SOLVE() will return still has a problem that there may be zeroes before the most significant bit.
  7. So we have to remove all the zeros before the most significant bit.
  8. While ARR[i]==0 erase the digit.
  9. Now return the ARR.
Time Complexity

O(N) where N is the length of the array.

 

As we are making a total of N calls in the recursive function.

Space Complexity

O(N) where N is the length of the array.

 

As we are using recursion stack so our space complexity arises to O(N).

Code Solution
(100% EXP penalty)
Increase Number By 1
Full screen
Console