Add Binary, Add Two Numbers

Add Binary

Given two binary strings, return their sum (also a binary string).
For example,
a = “11”
b = “1”
Return “100”.

Solution

Note:Int can be converted to String for manipulation, however, converting String to Int might cause overflow errors.

    public String addBinary(String a, String b) {
		
		if(a==null|a.length()==0)
			return b;
		if(b==null|b.length()==0)
			return a;
//switch a,b if a is shorter than b 
        if(a.length() < b.length()){
            String temp = a;
            a = b;
            b = temp;
        }
        
        int m = a.length()-1;
        int n = b.length()-1;
        int res = 0;
        String rst = "";
        
//Add from last digit
        while(n >= 0){
            int sum = (int)(a.charAt(m) - '0') + (int)(b.charAt(n) - '0') + res;
            rst = String.valueOf(sum % 2) + rst;
            res = sum / 2;
            m --;
            n --;
        }
//Add the longer digits        
        
        while(m >= 0){
            int sum = (int)(a.charAt(m) - '0') + res;
            rst = String.valueOf(sum % 2) + rst;
            res = sum / 2;
            m --;
        }       
        
//Don't forget the highest digit 
        if (res == 1)
            rst = "1" + rst;
        return rst;
    }

---

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution

We don’t have to compare the length of two lists an match digits since we are given reversed order. So just add each pair and the rest, pay attention to the last carries.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        if(l1==null && l2==null) return null;
        ListNode head=new ListNode(0);
        ListNode cur=head;
        int carries=0;
        while(l1!=null&&l2!=null){
            int sum=l1.val+l2.val+carries;
            carries=sum/10;
            ListNode n=new ListNode(sum%10);
            cur.next=n;
            
            l1=l1.next;
            l2=l2.next;
            cur=cur.next; 
        }
        
        while(l1!=null){
            int sum=carries+l1.val;
            cur.next=new ListNode(sum%10);
            carries=sum/10;
            cur=cur.next;
            l1=l1.next;
        }
        
        while(l2!=null){
            int sum=carries+l2.val;
            cur.next=new ListNode(sum%10);
            carries=sum/10;
            cur=cur.next;
            l2=l2.next;
        }
        
        if(carries!=0){
            cur.next=new ListNode(carries%10);
        }
        
        return head.next;
           }