Saturday, January 30, 2010

Add two numbers representened in lists (with carry)

You are given two numbers with a strange list representation such as the below. Add them with carry. Find the optimal solution in space and time.

Num 1 = 123456
Num 2= 1234

1. This is a quite cute puzzle! It can be done in constant space and linear time by "predicting" the carries.

If I am summing two digits I can determine the current carry by looking at the next two digits: if they sum up to 10 or more then the carry is 1, if their sum is less than 9 then carry is 0. Finally, if their sum is
exactly 9, I go forward in both lists (recording the current position) and look for the first couple of digits whose sum is not 9, then propagate the carry backward.

2. One more point - we need to assume 0s in the shorter list to resize it to the length of longer one.

3. There is another solution that shares the same time and space characteristics as the one outlined above. The solution above requires the following from an implementation perspective:

1. Walk thru' both lists to determine the shorter one O(m+n)
2. Insert elements into the shorter list to make them equal size O(n-m)
3. Walk the list to sum O(n).

The solution I had was to simply reverse both the lists (amounts to 1 and 2 above). Simply walk the list and sum the numbers until you have hit the end of the largest list.

Pseudo Code:

firstList->reverseList();
secondList->reverseList();

int sum = 0;
int i =1;

Node* l1 = firstList->getHead();
Node* l2 = secondList->getHead();

while (l1 && l2)
{
int res = l1->getIntValue() + l2->getIntValue();
sum = res*i + sum;
i *= 10;
l1 = l1->getNext();
l2 = l2->getNext();
}

//
// if the lists are of unequal sizes, walk the residual list using the same // algorithm above.
//