Add 1 to the Number Represented as Array using Recursive Approach

Given an array which is a collection of non-negative number represented as an array of digits, add 1 to the number (increment the number represented by the digits ). The digits are stored such that the most significant digit is the first element of the array.

To add 1 to the number represented by digits

• Given array from the end, addition means rounding of the last no 4 to 5.

• If the last elements 9, make it 0 and carry = 1.

• For the next iteration check carry and if it adds to 10, do the same as step 2.

• After adding carry, make carry = 0 for the next iteration.

• If the vectors add and increase the vector size, append 1 in the beginning.

Suppose an array contains elements [7, 6, 3, 4] then the array represents decimal number 1234 and hence adding 1 to this would result in 7635. So new array will be [7, 6, 3, 5].

Examples

Input: [7, 6, 9, 9]
Output: [7, 7, 0, 0]
Input: [4, 1, 7, 8, 9]
Output: [4, 1, 7, 9, 0]

Explanation Add 1 to the last element of the array, if it is less than 9. If the element is 9, then make it 0 and recurse for the remaining element of the array.

Example

#include <iostream>
using namespace std;
void sum(int arr[], int n) {
   int i = n;
   if(arr[i] < 9) {
      arr[i] = arr[i] + 1;
      return;
   }
   arr[i] = 0;
   i--;
   sum(arr, i);
   if(arr[0] > 0) {
      cout << arr[0] << ", ";
   }
   for(int i = 1; i <= n; i++) {
      cout << arr[i];
      if(i < n) {
         cout << ", ";
      }
   }
}
int main() {
   int n = 4;
   int arr[] = {4, 1, 7, 8, 9};
   sum(arr, n);
   return 0;
}