Add Two Numbers

Moderate
0/80
Average time to solve is 20m
201 upvotes
Asked in companies
Goldman SachsInformaticaFacebook

Problem statement

You are given two non-negative numbers 'num1' and 'num2' represented in the form of linked lists.


The digits in the linked lists are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit.


Calculate the sum of the two numbers and return the head of the sum list.


Example : 
Input:
'num1' : 1 -> 2 -> 3 -> NULL
'num2' : 4 -> 5 -> 6 -> NULL

Output: 5 -> 7 -> 9 -> NULL

Explanation: 'num1' represents the number 321 and 'num2' represents 654. Their sum is 975.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer 'm', the number of elements in 'num1'.
The second line contains 'm' integers, the elements of the first singly linked list / digits of 'num1'.
The third line contains a single integer 'n', the number of elements in 'num2'.
The fourth line contains 'n' integers, the elements of the second singly linked list / digits of 'num2'.


Output Format: 
Return the sum linked list.


Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1 :
3
1 2 3
3
4 5 6


Sample Output 1 :
5 7 9


Explanation for Sample Input 1 :
'num1' represents the number 321 and 'num2' represents 654. Their sum is 975.


Sample Input 2 :
2
0 1
1
0


Sample Output 2 :
0 1


Explanation for Sample Input 2 :
'num1' represents 10 and 'num2' represents 0. Their sum is 10.


Sample Input 3 :
1
2
2
9 9


Sample Output 3 :
1 0 1


Explanation for Sample Input 3 :
'num1' represents 2 and 'num2' represents 99. Their sum is 101.


Expected Time Complexity :
The expected time complexity is O('m' + 'n').


Constraints :
1 <= 'm', 'n' <= 5 * 10^4
0 <= 'data' in any Linked List node <= 9

The numbers do not contain any leading zeros.
If the number is zero, then there is one node having 'data' = 0.

Time Limit: 1 sec
Hint

Can you perform the addition by recursively traversing through the lists?

Approaches (3)
Recursion
  • A simple approach could be to recursively add the nodes of the linked list while keeping track of the carry generated.
  • The idea behind this approach is the same as finding the sum of two numbers manually on a paper, where we start by adding the LSD and move on till the MSD. Also, keeping track of the carry generated in every iteration.
  • As the linked lists represent the numbers in reverse order, the LSD occurs at the starting of the list and MSD occurs at the ending.
  • So to perform the addition, we can add the corresponding nodes (i.e. nodes present at the same position) of the two linked lists to generate the resulting digit in the sum list.
  • While adding, it is possible that the sum of the two nodes is greater than 9. This will generate a carry that needs to be added to the next significant digit.
  • In case one of the lists has more number elements than the other, then we consider the remaining values of the other list as 0.

The steps are as follows:

  • Let the recursive function be addTwoNumbersHelper('node1', 'node2', 'carry') which takes the current node of the first list, the current node of the second list, and the carry generated from the previous iteration/addition.
  • Initially, we call the function as addTwoNumbersHelper('num1', 'num2', 0).
  • Base Condition: If 'node1' = NULL AND 'node2' = NULL AND 'carry' = 0, return NULL.
  • Let 'val1' and 'val2' denote the value stored in the current nodes of the two linked lists, respectively. And 'next1' and 'next2' denote the pointers to the node present after the current nodes of the two linked lists, respectively.
  • If 'node1' = NULL, then the list 1 is empty so consider the current node’s value as zero i.e. 'val1' = 0, and the node after the current node as NULL i.e. 'next1' = NULL.
  • Otherwise, list 1 is not empty. So, 'val1' = 'node1'.data and 'next1' = 'node1'.next.
  • If 'node2' = NULL, then the list 2 is empty so consider the current node’s value as zero i.e. 'val2' = 0 and the node after the current node as NULL i.e. 'next2' = NULL.
  • Otherwise, list 2 is not empty. So, 'val2' = 'node2'.data  and 'next2' = 'node2'.next.
  • Add the values in the current nodes of the two linked lists along with the carry to generate the resulting sum. Store it in a variable, say sum i.e. 'sum' = 'val1' + 'val2' + 'carry'.
  • Get the next node of the sum list by creating a new node having data = 'sum'%10. Store the new node in a variable say, 'sumNode'.
  • Recursively call the function to generate the remaining nodes of the sum list as:
    • 'sumNode'.next = addTwoNumbersHelper('next1', 'next2', 'sum' / 10)
  • Return 'sumNode'.
Time Complexity

O('m' + 'n'), where 'm' and 'n' are the lengths of the linked lists.

We are traversing both the linked lists completely and it takes O(L) (where L is the number of nodes in the list) time to traverse each list.

Hence the time complexity is O('m' + 'n').

Space Complexity

O(Max('m', 'n')), where 'm' and 'n' are the lengths of the linked lists.

Extra space is required for the recursion stack and also for storing the sum list. The maximum depth of the stack and the length of the sum list is Max(Length of 'num1', Length of 'num2') + 1.

Hence the space complexity is O(Max('m', 'n')).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Add Two Numbers
Full screen
Console