Wednesday, December 24, 2014

Find the sum of numbers whose digits are represented by linked list entries. Output the result as a linked list.

Q. You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1st digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example

Input: (7 -> 1 -> 6) +  (5 -> 9 -> 2). That is, 617 + 295.
Output: 2 -> 1 -> 9. That is, 912.

FOLLOW UP

Suppose the digits are stored in forward order. Repeat the above problem.

Example

Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is, 617 + 295.
Output: 9 -> 1 -> 2. That is, 912.

Source:

import java.util.Stack;

public class Code{
    private static Stack<Integer> getDigits(int number){
        Stack<Integer> stack = new Stack<>();
        int t = 10;
        while(number!=0){
            int q  = number % t;
            stack.push(q);
            number = number / 10;
        }
        return stack;
    }
    
    public static int getNumberReverseOrder(LinkedList<Integer> ll){
        LinkedList.Node p = ll.head;
        int number = (int)p.value;
        int i=10;
        p = p.next;
        while(p != null){
            number += (int)p.value * i;
            i *= 10;
            p = p.next;
        }
        return number;
    }
    
    public static int getNumberForwardOrder(LinkedList<Integer> ll){
        int number = getNumberReverseOrder(ll);
        StringBuilder num = new StringBuilder();
        num.append(Integer.toString(number));
        num.reverse();
        return Integer.parseInt(num.toString());
    }
    
    private static LinkedList<Integer> makeListForReverseOrder(int number){
        Stack<Integer> digits = getDigits(number); 
        
        LinkedList<Integer> ll = new LinkedList<>();
        ll.head = ll.new Node();
        LinkedList.Node temp;
        
        while(true){ 
            ll.head.value = digits.pop();
            if(digits.isEmpty()) break;
            temp = ll.head;
            ll.head = ll.new Node();
            ll.head.next = temp;
        }  
        return ll;
    }
    
    private static LinkedList<Integer> makeListForForwardOrder(int number){
        Stack<Integer> digits = getDigits(number); 
        
        LinkedList<Integer> ll = new LinkedList<>();
        LinkedList.Node temp;
        ll.head = ll.new Node();
        temp = ll.head;
        while(true){
            temp.value = digits.pop();
            if(digits.isEmpty())break;
            temp.next = ll.new Node();
            temp = temp.next;
        }
        return ll;
    }
    
    public static void main(String[] args){
        int n1 = 999;
        int n2 = 773;
        
        //Reverse Order Test
        LinkedList<Integer> list1 = makeListForReverseOrder(n1), 
                            list2 = makeListForReverseOrder(n2),
                            result;   
        int sum = getNumberReverseOrder(list1)+getNumberReverseOrder(list2); 
        result = makeListForReverseOrder(sum); 
        System.out.println(result); 
        
        //Forward Order Test
        list1 = makeListForForwardOrder(n1); 
        list2 = makeListForForwardOrder(n2); 
        sum = getNumberForwardOrder(list1)+getNumberForwardOrder(list2);
        result = makeListForForwardOrder(sum);
        System.out.println(result); 
    }
}


public class LinkedList <T>{
    
    Node head;
    
    public class Node{
        Node next;
        T value;
        
        Node(T value){this.value = value;}
        Node(){}
    }
    
    public void add(T value){
        if(head==null){head = new Node(value); return;}
        Node t = head;
        while(t.next!=null){t = t.next;}
        t.next = new Node(value); 
    }
    
    public boolean isEmpty(){
        return head==null;
    }
    
    @Override
    public String toString(){
        StringBuilder bf = new StringBuilder();
        Node t = head;
        while(t!=null){
            bf.append(t.value).append(" -> ");
            t = t.next;
        }
        bf.delete(bf.length()-4, bf.length());
        return bf.toString();
    }
}

Output:

2 -> 7 -> 7 -> 1
1 -> 7 -> 7 -> 2

Approach  #2

Compute the sum on-the-fly and build the list as digits are calculated.

In this case, care must be taken if the digit length of the numbers is different. Padding with extra zeroes is required.

Source:

import java.util.Stack;

public class Code{
     
    private static Stack<Integer> getDigits(int number){
        Stack<Integer> stack = new Stack<>();
        int t = 10;
        while(number!=0){
            int q  = number % t;
            stack.push(q);
            number = number / 10;
        }
        return stack;
    }  
    
    //Method #2
    
    public static LinkedList<Integer> addReverse(LinkedList<Integer> l1, LinkedList<Integer> l2){
        LinkedList<Integer> result = new LinkedList<>(); 
        padWithZerosRO(l1, l2);
        System.out.println("list 1 = "+l1+"\nlist 2 = "+l2);
        addReverse(l1.head, l2.head, result, 0);
        return result;
    }
    
    private static void addReverse(LinkedList<Integer>.Node l1, LinkedList<Integer>.Node l2, LinkedList<Integer> result, int carry){
        if(l1 == null){
            if(carry!=-1)result.add(carry);
            return;
        }
        int sum = l1.value + l2.value + carry;
        result.add(sum%10);
        carry = sum/10;
        if(l1.next == null && l2.next == null && sum < 10)carry = -1;
        addReverse(l1.next, l2.next, result, carry);
    }
        
    private static void padWithZerosRO(LinkedList<Integer> l1, LinkedList<Integer> l2){
        LinkedList<Integer>.Node n1 = l1.head, n1p, n2 = l2.head, n2p;
        while(true){
            n1p = n1;
            n1 = n1.next;
            
            if(n1 == null && n2!=null){
                while(n2!= null && n2.next!=null){
                    n1 = l1.new Node(0);
                    n1p.next = n1;
                    n1p = n1;
                    n2 = n2.next; 
                }
                break;
            }
            
            n2p = n2;
            n2 = n2.next;
            
            if(n2==null && n1!=null){
                while(n1!=null){
                    n2 = l2.new Node(0);
                    n2p.next = n2;
                    n2p = n2;
                    n1 = n1.next;
                }
                break;
            }
            
            if(n1==null && n2==null)break;
        }
    }
    
    
    //FOLLOW UP
    private static void padWithZerosFO(LinkedList<Integer> l1, LinkedList<Integer> l2){
        LinkedList<Integer>.Node n1 = l1.head, n1p, n2 = l2.head, n2p;
        while(true){
            n1p = n1;
            n1 = n1.next;
            
            if(n1 == null && n2!=null){
                while(n2!= null && n2.next!=null){ 
                    addHead(l1, 0);
                    n2 = n2.next; 
                }
                break;
            }
            
            n2p = n2;
            n2 = n2.next;
            
            if(n2==null && n1!=null){
                while(n1!=null){
                    addHead(l2, 0);
                    n1 = n1.next;
                }
                break;
            }
            
            if(n1==null && n2==null)break;
        }
    }
    
    public static LinkedList<Integer> addForward(LinkedList<Integer> l1, LinkedList<Integer> l2){
        LinkedList<Integer> result = new LinkedList<>(); 
        padWithZerosFO(l1, l2);
        System.out.println("list 1 = "+l1+"\nlist 2 = "+l2);
        addForward(l1.head, l1.head, l2.head, result);
        return result;
    }
    
    private static int addForward(LinkedList<Integer>.Node l1Head, LinkedList<Integer>.Node l1, LinkedList<Integer>.Node l2, LinkedList<Integer> result){
        if(l1 == null)return 0;
        
        int carry = addForward(l1Head, l1.next, l2.next, result);
        int sum = l1.value + l2.value + carry;
        addHead(result, sum%10);
        carry = sum / 10; 
        if(l1 == l1Head && carry != 0)addHead(result, carry);
        return carry;
    }
    
    private static void addHead(LinkedList<Integer> ll, int value){
        LinkedList<Integer>.Node newHead = ll.new Node(value);
        newHead.next = ll.head;
        ll.head = newHead;  
    } 
    
    private static LinkedList<Integer> makeListForReverseOrder(int number){
        Stack<Integer> digits = getDigits(number); 
        
        LinkedList<Integer> ll = new LinkedList<>();
        ll.head = ll.new Node();
        LinkedList.Node temp;
        
        while(true){ 
            ll.head.value = digits.pop();
            if(digits.isEmpty()) break;
            temp = ll.head;
            ll.head = ll.new Node();
            ll.head.next = temp;
        }  
        return ll;
    }
    
    private static LinkedList<Integer> makeListForForwardOrder(int number){
        Stack<Integer> digits = getDigits(number); 
        
        LinkedList<Integer> ll = new LinkedList<>();
        LinkedList.Node temp;
        ll.head = ll.new Node();
        temp = ll.head;
        while(true){
            temp.value = digits.pop();
            if(digits.isEmpty())break;
            temp.next = ll.new Node();
            temp = temp.next;
        }
        return ll;
    }
    
    public static void main(String[] args){
        int n1 = 99999;
        int n2 = 999990999;
        
        //Reverse Order Test
        LinkedList<Integer> list1 = makeListForReverseOrder(n1), 
                            list2 = makeListForReverseOrder(n2),
                            result;    
        
        System.out.println(addReverse(list1, list2)+"\n\n");  
        
        //Forward Order Test
        list1 = makeListForForwardOrder(n1); 
        list2 = makeListForForwardOrder(n2);   
        
        System.out.println(addForward(list1, list2)); 
    }
}

Output:

list 1 = 9 -> 9 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 0
list 2 = 9 -> 9 -> 9 -> 0 -> 9 -> 9 -> 9 -> 9 -> 9
8 -> 9 -> 9 -> 0 -> 9 -> 0 -> 0 -> 0 -> 0 -> 1


list 1 = 0 -> 0 -> 0 -> 0 -> 9 -> 9 -> 9 -> 9 -> 9
list 2 = 9 -> 9 -> 9 -> 9 -> 9 -> 0 -> 9 -> 9 -> 9
1 -> 0 -> 0 -> 0 -> 0 -> 9 -> 0 -> 9 -> 9 -> 8

No comments:

Post a Comment