Amazon Interview 1: Problem 2

Problem 2: Given two linked lists. Each node stores a single digit. Each linked list this way represents a decimal number, with number of digits = number of nodes in the list. You need to add them to produce a third list which represents the sum of the numbers.

Problem statement would be complete only if we know the how decimal numbers are represented in the list.

To represent .123 the list is 1 -> 2-> 3

To add 2 numbers, you must consider the following scenario:

List 1 = 4 -> 5 -> 6
List 2 = 6 -> 9

Returned list should be 1 -> 1 -> 4 -> 6 (Though if this is considered only decimal number, it would be incorrect) but for time being let's consider this as a solution.

Solution 1: Modify the shorter list to append the '0' (Zero) to make both the lists size equal. For each list reach to ith location (1 <= i <= N ) starting from the Size of the list and add both the lists. If sum is greater than one use carry to add (i - 1) position.

List 1 => 4 -> 5 -> 6
List 2 => 6 -> 9 -> 0

When I = 3 (Iteration to reach 3rd position = 3)
List 3 => 6
Carry = 0

When I = 2 (Iteration to reach 3rd position = 2)
List 3 => 4 -> 6
Carry  = 1

When I = 1 (Iteration to reach 3rd position = 1)
List 3 => 1 -> 4 -> 6
Carry = 1

Exit the loop and add carry to list 3
List 3 => 1 -> 1 -> 4 -> 6

Time Complexity: 3 + 2 + 1 (N = 3)
Time Complexity for N elements: N + (N-1) + .... + 1 = N(N+1)/2 = O(N*N)

Time complexity of the above solution is O(N*N)

Solution 2: You can even reverse the lists and add them simply. But reversing the list would also require O(N*N) time complexity, and you would change the original structure of the input which is not desirable.

Solution 3: Here is another idea which performs better in normal circumstances, whereas in worst case it has same O(N*N) time complexity.

Logic
 method add start
  input list1 and list2
  minLength = find the smaller length of both the list
  assign a boolean array of len = minLength
  create a node with sum of list1 and list 2 digit mod 10
  array[0] = assign true if sum is greater than zero
  repeatTill = array[0] == true? 0:-1;
  for element from 1 to min length
   create a node with sum of list1 and list 2 digit mod 10
   array[element] = assign true if sum is greater than zero  
   repeatTill = array[element] == true? element:repeatTill;
  end for
  assign the remaining elements of the longer list to new list
  call recursive method to update the carries
 end
 
 method updateCarries start
  input list3, boolean[] array, repeatTill
  if repeatTill is negative then
   return list3
  end if
  if array[0] is true then
   add Node with digit 1 at front of the list
  end if
  for element from 1 to repeatTill
   if array[element] is true then
    assign repeatTill if array[element-1] is true
    update values
   end if
  end for
  return call updateCarries
 end

This solution's best case is O(N) when there is no carry in these two digits. For Example when 123 and 234 are added. In this case, loop is iterated only once.

Whereas in the worst case it will run for O(N*N). That would be most unusual addition. For Example when 9999 and 0001 are added. In this case, N*(N+1)/2 elements are accessed.

Java code for the solution is as following:

Java Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Problem: Given two linked lists. Each node stores a single digit. Each linked
 * list this way represents a decimal number, with number of digits = number of
 * nodes in the list. You need to add then to produce a third list which
 * represents the sum of the numbers.
 * 
 * E.G. LinkedList 1 -> 2 -> 6 LinkedList 3 -> 8
 * 
 *
 */
public class SumDecimal {

 /**
  * This method reads the input and prepares the array and call the relevant
  * method.
  * 
  * @param args
  * @throws IOException
  */
 public static void main(String[] args) throws IOException {

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String line = br.readLine();
  /**
   * N is the number of test cases.
   */
  int N = Integer.parseInt(line);
  for (int i = 0; i < N; i++) {
   String[] list1Values = br.readLine().split(" ");
   String[] list2Values = br.readLine().split(" ");
   Node list1 = null;
   for (int index = list1Values.length - 1; index >= 0; index--) {
    Node n = new Node(Integer.parseInt(list1Values[index]));
    n.next = list1;
    list1 = n;
   }
   Node list2 = null;
   for (int index = list2Values.length - 1; index >= 0; index--) {
    Node n = new Node(Integer.parseInt(list2Values[index]));
    n.next = list2;
    list2 = n;
   }
   Node list3 = add(list1, list2);
   System.out.println(list3);
  }
 }

 private static Node add(Node list1, Node list2) {
  int minLength = 1;
  Node l1 = list1;
  Node l2 = list2;
  while (l1.next != null && l2.next != null) {
   minLength++; // M or N whatever is smaller.
   l1 = l1.next;
   l2 = l2.next;
  }
  boolean[] carries = new boolean[minLength];
  Node list3 = new Node((list1.digit + list2.digit) % 10);
  Node list = list3;
  carries[0] = (list1.digit + list2.digit) / 10 == 0 ? false : true;
  int toMove = carries[0] ? 0 : -1;
  for (int index = 1; index < minLength; index++) {
   Node n = new Node((list1.next.digit + list2.next.digit) % 10);
   carries[index] = (list1.next.digit + list2.next.digit) / 10 == 0 ? false : true;
   list1 = list1.next;
   list2 = list2.next;
   list3.next = n;
   list3 = list3.next;
   toMove = carries[index] ? index : toMove;
  }
  if (list1.next != null) {
   list3.next = list1.next;
  } else {
   list3.next = list2.next;
  }
  list = updateCarries(list, carries, toMove);
  return list;
 }

 private static Node updateCarries(Node list3, boolean[] carries, int toMove) {
  if (toMove == -1)
   return list3;
  int nextMove = -1;
  Node list = list3;
  if (carries[0]) {
   Node n = new Node(1);
   n.next = list3;
   list = n;
   carries[0] = false;
  }
  for (int index = 1; index <= toMove; index++) {
   if (carries[index]) {
    int sum = list3.digit + 1;
    carries[index - 1] = sum == 10 ? true : false;
    list3.digit = sum % 10;
    carries[index] = false;
    nextMove = carries[index - 1] ? index - 1 : nextMove;
   }
   list3 = list3.next;
  }
  return updateCarries(list, carries, nextMove);
 }

 static class Node {
  int digit;
  Node next;

  Node(int digit) {
   this.digit = digit;
  }

  public String toString() {
   return (next == null) ? digit + "" : digit + " " + next.toString();
  }
 }

}

Input
7
1 2 3
2 3 4
3 4 5
3 4 5
9 9 9
0 0 1
9 0 0
1 9 9
9 8 1
1 2
1 2 6 8 9 6 7 8 9
9
1 2 6 8 9 6 7 8 9
9 8 4 2 1 4 3 8 7

Output
3 5 7
6 9 0
9 9 9
1 0 9 9
1 1 0 1
1 0 2 6 8 9 6 7 8 9
1 1 1 1 1 1 1 1 7 6

If you feel that something is not correct with the solution, let me know. I would try to fix the problem.