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.
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.
