Adding Number using Recursion


  • 1
    G

    Intuition
    Each digit is stored in a node and its positive integer

    Algorithm

    First we need to consider that two numbers could be of different length, and we need to add each digit of the List from right to left.

    First step of the algorithm will be to find the length of the list and if the list is not same size, we will pad 0 to the front of the list to make it same length.

    eg: if input is (7 -> 2 -> 4 -> 3)  and  (5 -> 6 -> 4)
          we will pad one zero to the second input and it will be (0->5->6->4)
    

    We will maintain a result list and will replace the sum of the digits with the front node of the result list and will add the carry to the front of the result list.

    Since we are adding the carry also to the result list and when we start we will not have any carry, so we will initialize the result list with zero.

    we will call our add method recursively with each node and once we reach to end of the list we will add the digits in two nodes and carry.
    If the sum is greater than 9 we will find the reminder and will add to the Result List front and will add carry to the Result List after that. Other wise we will add the sum and carry as 0 to the Result list

    When we start the Result List will have only 0.

    First we will add the digits 3 + 4 + 0 (result node ) = 7
    here 0 is the carry that we initialized with 0.
    here the sum is 7 and its less than 9 so we will replace the front of the result with 7 and will add 0(carry) to the front of the result

    Result List = 0 -> 7

    next sum will be

    4+6+0 = 10

    here we have 1 as carry, we will replace the exiting carry in the result List with 0 and will add carry(1) to the front. So the result list will look like

    Result List = 1 -> 0 -> 7

    Since we are adding the carry as zero if there is no carry in the end we will have an additional zero at the front of the result List. We will remove this manually

    Java

    class Solution {
       public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       
           // Find the lenght of the list
           int len1 = length(l1);
           int len2 = length(l2);
           
           //Pad zero if the lenght is not same
           if(len1>len2){
               l2 = appendZero(l2,len1-len2);
           }else if(len2>len1){
               l1 = appendZero(l1,len2-len1);
           }
           
           //Initialize result with zero assuming 0 as the first carry
           ListNode result = new ListNode(0);
           
           result = addNodes(l1,l2,result);
           
           // remove the 0 from the front of the result if the sum of the last digits didn't have any carry
           if(result.val == 0){
               result = result.next;
           }
           return result;
       }
       private int length(ListNode node){
           int count = 0;
           while(node != null){
               node = node.next;
               count++;
           }
           return count;
       }
       private ListNode appendZero(ListNode node,int num){
           for(int i=0;i<num;i++){
               ListNode tempNode = new ListNode(0);
               tempNode.next=node;
               node=tempNode;
           }
           return node;
       }
       
       private ListNode addNodes(ListNode l1,ListNode l2,ListNode resultNode){
           
           if(l1.next != null){
               resultNode = addNodes(l1.next,l2.next,resultNode);
           }
           
           // sum of the digits and carry from the last addition.
           int sum = l1.val+l2.val+resultNode.val;
           int carry = 0;
           int deci = sum;
           
           if(sum >= 10){
               carry = sum/10;
               deci = sum%10;
           }
           //replace the last carry with the sum.
           resultNode.val = deci;
           
           // careate a new node for carry and add to the front
           ListNode node = new ListNode(carry);
           node.next = resultNode;
           resultNode = node;
           
           
           return resultNode;
       }
    }
    

    Complexity Analysis

    • Time complexity will be O(n) since we need to traverse through each node at least once

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.