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.
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.
This is a quite cute puzzle! It can be done in constant space and linear time by "predicting" the carries.
ReplyDeleteIf 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.
One more point - we need to assume 0s in the shorter list to resize it to the length of longer one.
ReplyDeleteThere 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:
ReplyDelete1. 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.
//