Add Two (Binary) Numbers | N00tc0d3r

Add Two (Binary) Numbers | N00tc0d3r

Add Two Numbers in Linked List (Stored in Reverse Order)

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.

For example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) => Output: 7 -> 0 -> 8
Since the input lists are already in reverse order, we don't need to worry about carry here.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  if (l1==null) return l2;
  if (l2==null) return l1;
  int carry = 0;
  ListNode head=null, cur=null;
  while (l1!=null || l2!=null) {
    int sum = carry;
    if (l1!=null) {
      sum+=l1.val;
      l1 = l1.next;
    }
    if (l2!=null) {
      sum+=l2.val;
      l2 = l2.next;
    }
    if (cur==null) { // first node
      cur = new ListNode(sum%10);
      head = cur;
    } else {
      cur.next = new ListNode(sum%10);
      cur = cur.next;
    }
    carry = sum / 10;
  }// end-while
  if (carry>0) cur.next = new ListNode(carry);
  return head;
}

Add Two Numbers in Linked List
This time you are given two linked lists representing two non-negative numbers. Each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

For example: Input: (3 -> 4 -> 2) + (4 -> 6 -> 5) => Output: 8 -> 0 -> 7

Solution
Now the digits are stored in plain order and thus we need to consider how to handle carry.private int length(ListNode ll) {
     int len = 0;
     while (ll != null) {
       ++len;
       ll = ll.next;
     }
     return len;
   }
 
   // The length of l1 >= the lenghth of l2 and n is the difference
   private int addRecursive(ListNode l1, int n, ListNode l2, ListNode pre) {
     if (l1 == null && l2 == null) {
       return 0;
     }
     pre.next = new ListNode(0);
     int sum = l1.val;
     if (n <= 0) {
       sum += l2.val;
       sum += addRecursive(l1.next, 0, l2.next, pre.next);
     } else {
       sum += addRecursive(l1.next, n-1, l2, pre.next);
     }
     pre.val = sum % 10;
     return sum / 10;
   }
 
   // Digits in the two lists are in forward order.
   // i.e. 345 = 3 -> 4 -> 5
   private ListNode addTwoNumbersRecur(ListNode l1, ListNode l2) {
     int n1 = length(l1), n2 = length(l2);
     ListNode dummy = new ListNode(0);
     if (n1 >= n2) {
       dummy.val = addRecursive(l1, n1-n2, l2, dummy);
     } else {
       dummy.val = addRecursive(l2, n2-n1, l1, dummy);
     }
     return (dummy.val > 0) ? dummy : dummy.next;
   }
Iterative solution:
   // Digits in the two lists are in forward order.
   // i.e. 345 = 3 -> 4 -> 5
   private ListNode addTwoNumbersIter(ListNode l1, ListNode l2) {
     ListNode dummy = new ListNode(0), last = dummy, cur = dummy;
     int n1 = length(l1), n2 = length(l2);
     if (n1 < n2) {
       ListNode tmp = l1; l1 = l2; l2 = tmp;
       int n = n1; n1 = n2; n2 = n;
     }
 
     while (n1 > n2) {
       cur.next = new ListNode(l1.val);
       cur = cur.next;
       if (cur.val < 9) last = cur;
       l1 = l1.next;
       --n1;
     }
 
     while (l1 != null) {
       int sum = l1.val + l2.val;
       l1 = l1.next;
       l2 = l2.next;
       cur.next = new ListNode(sum % 10);
       cur = cur.next;
       if (sum / 10 > 0) {
         while (last != cur) {
           last.val = (++last.val) % 10;
           last = last.next;
         }
       } else if (cur.val < 9) {
         last = cur;
       }
     }
 
     return (dummy.val > 0) ? dummy : dummy.next;
   }

Add Two Binary Strings
Given two binary strings, return their sum (also a binary string).
For example, a = "11", b = "1" => Return "100".   public String addBinary(String a, String b) {
    StringBuilder aa = new StringBuilder(a);
    aa.reverse();
    StringBuilder bb = new StringBuilder(b);
    bb.reverse();
    /* 0 + 0 + 0/1 (cap) = 00/01
     * 1 + 1 + 0/1 = 10/11
     * 0 + 1 + 0/1 = 01/10
     */
    char carry = '0';
    StringBuilder res = new StringBuilder();
    int i=0;
    while (i<aa.length() && i<bb.length()) {
      if (aa.charAt(i) == bb.charAt(i)) { // 0+0 or 1+1
        res.append( carry );
        carry = aa.charAt(i);
      } else { // 0+1 or 1+0
        res.append( (carry=='0') ? '1' : '0' );
      }
      ++i;
    }// end-while-aa|bb
    /* 0 + 0/1 = 00/01, 1 + 0/1 = 01/10 */
    while (i<aa.length()) {
      if (aa.charAt(i) == '0') {
        res.append(carry);
        carry = '0';
      } else {
        res.append( (carry=='0') ? '1' : '0' );
      }
      ++i;
    }// end-while-aa  
    while (i<bb.length()) {
      if (bb.charAt(i) == '0') {
        res.append(carry);
        carry = '0';
      } else {
        res.append( (carry=='0') ? '1' : '0' );
      }
      ++i;
    }// end-while-bb
    if (carry=='1') res.append(carry);
    return res.reverse().toString();
  }


 public String addBinary(String a, String b) {
   String longer, shorter;
   int n, m;
   if (a.length() > b.length()) {
     n = a.length(); m = b.length();
     longer = a; shorter = b;
   } else {
     n = b.length(); m = a.length();
     longer = b; shorter = a;
   }
 
   StringBuilder res = new StringBuilder();
   res.append('0'); // dummy head
   // find the last zero
   int lastZero = 0;
   for (int i=0; i<n-m; ++i) {
     res.append(longer.charAt(i));
     if (longer.charAt(i) == '0') lastZero = res.length() - 1;
   }
   // calculate
   for (int i=n-m, j=0; j<m; ++i, ++j) {
     int sum = (longer.charAt(i) == '1') ? 1 : 0;
     sum += (shorter.charAt(j) == '1') ? 1 : 0;
     res.append(sum & 1);
     int cur = res.length() - 1;
     if ((sum >> 1) > 0) {
       res.setCharAt(lastZero, '1');
       for (int k=lastZero+1; k<cur; ++k) {
         res.setCharAt(k, '0');
       }
     }
     if (res.charAt(cur) == '0') lastZero = cur;
   }

   // check head
   if (res.charAt(0) == '0') res.deleteCharAt(0);
   return res.toString();
 }
Read full article from Add Two (Binary) Numbers | N00tc0d3r