 Register for our webinar

### How to Nail your next Technical Interview

1 hour 1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name  Step 1  Step 2
Congratulations!
You have registered for our webinar Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone  Step 1  Step 2 Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.  ## You may be missing out on a 66.5% salary hike* ### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.  ## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.  # Add Two Numbers Problem Statement

Write a function which adds two numbers `a` and `b`, represented as linked lists of size `lenA` and `lenB` respectively, and returns the sum of `a` and `b` in the form of a new linked list.

Ignoring the allocation of a new linked list, try to use constant memory when solving it.

A number is represented by a linked list, with the head of the linked list being the least significant digit. For example 125 is represented as 5->2->1, and 371 is represented as 1->7->3. Adding 5->2->1(125) and 1->7->3(371) should produce 6->9->4(496).

## Example One

``````{
"l_a": [7, 5, 2],
"l_b": [2, 0, 3]
}
``````

Output:

``````[9, 5, 5]
``````

As `l_a` = 7->5->2 means number 257 and `l_b` = 2->0->3 means number 302. Sum of 257 and 302 is 559 so, result will represent 9->5->5.

## Example Two

``````{
"l_a": [5, 8, 3],
"l_b": [9, 4, 1]
}
``````

Output:

``````[4, 3, 5]
``````

As `l_a` = 5->8->3 means number 385 and `l_b` = 9->4->1 means number 149. Sum of 385 and 149 is 534 so, result will represent 4->3->5.

## Notes

• There are two input parameters `l_a` and `l_b`, denoting linked lists representing numbers `a` and `b` respectively.
• Output is the head node of resultant linked list representing the sum of two numbers `a` and `b`.

Constraints

• 1 <= length of the input linked lists <= 100000
• 0 <= linked list node value <= 9
• Leading zeros will not appear in the input and will not be accepted in the output.
• No negative numbers.

We have provided three solutions. We will refer to the length of `l_a` and `l_b` as `lenA` and `lenB`, respectively.

# Add Two Numbers Solution 1: 1St Other

Let's have a look at an approach for having sum of two numbers `x` and `y` represented in decimal number system:

(Let us say string representation of number is `num_str`, then Least significant digit means digit represented by character at 0th index of `num_str` and Most significant digit means digit represented by character at `len(num_str) - 1`-th index of `num_str`).

• Add trailing zeroes to make the lengths of `x` and `y` equal(in decimal system). Let us say this length is `N`.
• Set `carryForward = 0` and `i = 0`.
• Add `i`-th significant digit of `x` and `y` and add `carryForward` to it(Let us say this sum `sumD`). If at `i`-th significant digit, `sumD` is greater than 9, we carry forward the tenth place digit of `sumD` to the next significant digit.
• Set `carryForward = sumD/10` and `i`-th significant digit of result to `sumD % 10`.
• `i = i + 1`, Repeat #3 till `i <= N - 1`.
• If `carryForward > 0`, set `N`-th significant digit of result as `carryForward`.
• Return result.

Now, as numbers are represented as a linked list, with the head of the linked list being the least significant digit, `i`-th node in linked list will be `i`-th least significant digit of the number. We need to start traversing linked lists corresponding to given two numbers starting from their heads and follow the above mentioned steps.

In this solution, we are creating an extra linked list to store resultant sum. In an actual interview, ignore the allocation of a new linked list, try to use constant memory when solving it. But if the interviewer asks for the solution which does not modify the input linked lists, then this is the expected solution.

## Time Complexity

O(max(lenA, lenB)).

As we are iterating over the given linked list `l_a` and `l_b` simultaneously in one iteration. Hence complexity is maximum of length of `l_a` and length `l_b`.

## Auxiliary Space Used

O(max(lenA, lenB)).

We are storing the resultant sum by creating a new linked list and the size of that newly created linked list can be `1 + max(lenA, lenB)`.

## Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(max(lenA, lenB))

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(max(lenA, lenB)) + O(max(lenA, lenB)) = O(lenA + lenB).

## Code For Add Two Numbers Solution 1: 1St Other

``````    /*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(max(lenA, lenB)).
* Auxiliary space: O(max(lenA, lenB)).
* Total space: O(lenA + lenB).
*/

// To store carry while adding two numbers
int carryForward = 0;
// Creating another singly linked list to store resultant sum
// To store head of result list, so we can return at the end of function

while(l_a != null || l_b != null) {
int l_a_data = 0;
if(l_a != null) {
l_a_data = l_a.value;
l_a = l_a.next;
}

int l_b_data = 0;
if(l_b != null) {
l_b_data = l_b.value;
l_b = l_b.next;
}

int sum = l_a_data + l_b_data + carryForward;
// If it's first node of result linkedlist then update data from -1 to sum % 10.
if(result.value == -1) {
result.value = sum % 10;
}
else{
// Create new next node in result linkedlist.
result.next = new_node;
result = result.next;
}
carryForward = sum / 10;
}
// If still carry is remaining then create another node in result linkedlist to store carry.
if(carryForward > 0){
result.next = new_node;
}
}
``````

# Add Two Numbers Solution 2: 2Nd Other

Approach will be as similar as explained other_solution1, but this approach is bit optimised in terms of space used as we will not create a new linked list to store the resultant sum rather than use one of the linked list `l_a` or `l_b`. We are iterating over given two linked lists to find out which one is longer and always making sure that `l_b` will always be the longer linked list to store the resultant sum if not then by swapping `l_a` and `l_b`.

## Time Complexity

O(lenA + lenB).

As we are iterating over two given linked lists `l_a` and `l_b`. Hence complexity is the sum of their lengths.

## Auxiliary Space Used

O(1).

We aren’t storing anything extra and using one of the two given linked list to store the resultant sum.

## Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(1)

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(1) + O(max(lenA, lenB)) = O(lenA + lenB).

## Code For Add Two Numbers Solution 2: 2Nd Other

``````    /*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(lenA + lenB).
* Auxiliary space: O(1).
* Total space: O(lenA + lenB).
*/

int lenA = 0, lenB = 0;

// Finding length of l_a
while (travA != null) {
lenA++;
travA = travA.next;
}

// Finding length of l_a
while (travB != null) {
lenB++;
travB = travB.next;
}

// if lenA > lenB, swap linked list pointers, so that after this point onwards,
// l_a contains smaller length linked list out of given two input linked lists
if (lenA > lenB) {
l_a = l_b;
l_b = l_temp;
}

int carryForward = 0;
travA = l_a;
travB = l_b;

while (true) {
// ith iteration of this loop denotes that we are processing ith significant digit
int l_a_data = (travA == null) ? 0 : travA.value;

// let say sumD = travB.value + travA.value + carryForward
travB.value += l_a_data + carryForward;

// Setting carryForward = sumD/10
carryForward = travB.value / 10;

// In ith iteration, setting ith significant digit of sum = sumD % 10
travB.value = travB.value % 10;

// Moving on to (i + 1)th significant digit
if(travA != null)
travA = travA.next;

if (travB.next == null){
// If carryForward > 0, Adding a node in l_b, which denotes new most significant digit of sum
// as there is no more digit to carry forward the carryForward
if (carryForward > 0) {
travB.next = new_node;
}
break;
}
travB = travB.next;
}

return l_b;
}
``````

# Add Two Numbers Solution 3: Optimal

Approach will be as similar as explained other_solution1, but this approach is optimised in terms of number of iterations and extra space used as we are storing the resultant value in one of the given two input linked list only so, we don’t require to create and allocate new linked list.

And we are not finding the longer linked list by iterating over given two linked list as we were doing in other_solution2 but when finding the resultant sum we are changing the pointer and appending the longer list’s remaining nodes to the linked list in which we are storing the resultant sum.

For more detailed explanation refer optimal_solution.

## Time Complexity

O(max(lenA, lenB)).

As we are iterating over the given linked list `l_a` and `l_b` simultaneously in one iteration. Hence complexity is maximum of length of `l_a` and length `l_b`.

## Auxiliary Space Used

O(1).

We aren’t storing anything extra and using one of the two given linked lists to store the resultant sum.

## Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(1)

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(1) + O(max(lenA, lenB)) = O(lenA + lenB).

## Code For Add Two Numbers Solution 3: Optimal

``````    /*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(max(lenA, lenB)).
* Auxiliary space: O(1).
* Total space: O(lenA + lenB).
*/

// We are storing resultant sum in l_b.
int carryForward = 0, sum = 0;
// To store carry and current sum.
// We are iterating till we reach at end of one of linkedlist.
// and update l_b with resultant sum.
while(true){
sum = l_a.value + l_b.value + carryForward;
l_b.value = sum % 10;
carryForward = sum / 10;
if(l_a.next == null || l_b.next == null){
break;
}
l_a = l_a.next;
l_b = l_b.next;
}
// If we reached the end of l_b but not of l_a, we can utilize the already created nodes
// of l_a by appending them to l_b.
if(l_a.next != null && l_b.next == null){
l_b.next = l_a.next;
}
// We iterate through remaining nodes of l_b and update it with sum of node and carry.
while(carryForward > 0 && l_b.next != null){
l_b = l_b.next;
sum = carryForward + l_b.value;
l_b.value = sum % 10;
carryForward = sum / 10;
}
// If still carry is remaining then we add extra node at tail of linkedlist l_b.
if(carryForward > 0){
l_b.next = new_node;
}
// Result will be head node of l_b (which is storing our resultant sum)
return result;
}
``````

We hope that these solutions to add two numbers problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Add Two Numbers Problem Statement

Write a function which adds two numbers `a` and `b`, represented as linked lists of size `lenA` and `lenB` respectively, and returns the sum of `a` and `b` in the form of a new linked list.

Ignoring the allocation of a new linked list, try to use constant memory when solving it.

A number is represented by a linked list, with the head of the linked list being the least significant digit. For example 125 is represented as 5->2->1, and 371 is represented as 1->7->3. Adding 5->2->1(125) and 1->7->3(371) should produce 6->9->4(496).

## Example One

``````{
"l_a": [7, 5, 2],
"l_b": [2, 0, 3]
}
``````

Output:

``````[9, 5, 5]
``````

As `l_a` = 7->5->2 means number 257 and `l_b` = 2->0->3 means number 302. Sum of 257 and 302 is 559 so, result will represent 9->5->5.

## Example Two

``````{
"l_a": [5, 8, 3],
"l_b": [9, 4, 1]
}
``````

Output:

``````[4, 3, 5]
``````

As `l_a` = 5->8->3 means number 385 and `l_b` = 9->4->1 means number 149. Sum of 385 and 149 is 534 so, result will represent 4->3->5.

## Notes

• There are two input parameters `l_a` and `l_b`, denoting linked lists representing numbers `a` and `b` respectively.
• Output is the head node of resultant linked list representing the sum of two numbers `a` and `b`.

Constraints

• 1 <= length of the input linked lists <= 100000
• 0 <= linked list node value <= 9
• Leading zeros will not appear in the input and will not be accepted in the output.
• No negative numbers.

We have provided three solutions. We will refer to the length of `l_a` and `l_b` as `lenA` and `lenB`, respectively.

# Add Two Numbers Solution 1: 1St Other

Let's have a look at an approach for having sum of two numbers `x` and `y` represented in decimal number system:

(Let us say string representation of number is `num_str`, then Least significant digit means digit represented by character at 0th index of `num_str` and Most significant digit means digit represented by character at `len(num_str) - 1`-th index of `num_str`).

• Add trailing zeroes to make the lengths of `x` and `y` equal(in decimal system). Let us say this length is `N`.
• Set `carryForward = 0` and `i = 0`.
• Add `i`-th significant digit of `x` and `y` and add `carryForward` to it(Let us say this sum `sumD`). If at `i`-th significant digit, `sumD` is greater than 9, we carry forward the tenth place digit of `sumD` to the next significant digit.
• Set `carryForward = sumD/10` and `i`-th significant digit of result to `sumD % 10`.
• `i = i + 1`, Repeat #3 till `i <= N - 1`.
• If `carryForward > 0`, set `N`-th significant digit of result as `carryForward`.
• Return result.

Now, as numbers are represented as a linked list, with the head of the linked list being the least significant digit, `i`-th node in linked list will be `i`-th least significant digit of the number. We need to start traversing linked lists corresponding to given two numbers starting from their heads and follow the above mentioned steps.

In this solution, we are creating an extra linked list to store resultant sum. In an actual interview, ignore the allocation of a new linked list, try to use constant memory when solving it. But if the interviewer asks for the solution which does not modify the input linked lists, then this is the expected solution.

## Time Complexity

O(max(lenA, lenB)).

As we are iterating over the given linked list `l_a` and `l_b` simultaneously in one iteration. Hence complexity is maximum of length of `l_a` and length `l_b`.

## Auxiliary Space Used

O(max(lenA, lenB)).

We are storing the resultant sum by creating a new linked list and the size of that newly created linked list can be `1 + max(lenA, lenB)`.

## Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(max(lenA, lenB))

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(max(lenA, lenB)) + O(max(lenA, lenB)) = O(lenA + lenB).

## Code For Add Two Numbers Solution 1: 1St Other

``````    /*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(max(lenA, lenB)).
* Auxiliary space: O(max(lenA, lenB)).
* Total space: O(lenA + lenB).
*/

// To store carry while adding two numbers
int carryForward = 0;
// Creating another singly linked list to store resultant sum
// To store head of result list, so we can return at the end of function

while(l_a != null || l_b != null) {
int l_a_data = 0;
if(l_a != null) {
l_a_data = l_a.value;
l_a = l_a.next;
}

int l_b_data = 0;
if(l_b != null) {
l_b_data = l_b.value;
l_b = l_b.next;
}

int sum = l_a_data + l_b_data + carryForward;
// If it's first node of result linkedlist then update data from -1 to sum % 10.
if(result.value == -1) {
result.value = sum % 10;
}
else{
// Create new next node in result linkedlist.
result.next = new_node;
result = result.next;
}
carryForward = sum / 10;
}
// If still carry is remaining then create another node in result linkedlist to store carry.
if(carryForward > 0){
result.next = new_node;
}
}
``````

# Add Two Numbers Solution 2: 2Nd Other

Approach will be as similar as explained other_solution1, but this approach is bit optimised in terms of space used as we will not create a new linked list to store the resultant sum rather than use one of the linked list `l_a` or `l_b`. We are iterating over given two linked lists to find out which one is longer and always making sure that `l_b` will always be the longer linked list to store the resultant sum if not then by swapping `l_a` and `l_b`.

## Time Complexity

O(lenA + lenB).

As we are iterating over two given linked lists `l_a` and `l_b`. Hence complexity is the sum of their lengths.

## Auxiliary Space Used

O(1).

We aren’t storing anything extra and using one of the two given linked list to store the resultant sum.

## Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(1)

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(1) + O(max(lenA, lenB)) = O(lenA + lenB).

## Code For Add Two Numbers Solution 2: 2Nd Other

``````    /*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(lenA + lenB).
* Auxiliary space: O(1).
* Total space: O(lenA + lenB).
*/

int lenA = 0, lenB = 0;

// Finding length of l_a
while (travA != null) {
lenA++;
travA = travA.next;
}

// Finding length of l_a
while (travB != null) {
lenB++;
travB = travB.next;
}

// if lenA > lenB, swap linked list pointers, so that after this point onwards,
// l_a contains smaller length linked list out of given two input linked lists
if (lenA > lenB) {
l_a = l_b;
l_b = l_temp;
}

int carryForward = 0;
travA = l_a;
travB = l_b;

while (true) {
// ith iteration of this loop denotes that we are processing ith significant digit
int l_a_data = (travA == null) ? 0 : travA.value;

// let say sumD = travB.value + travA.value + carryForward
travB.value += l_a_data + carryForward;

// Setting carryForward = sumD/10
carryForward = travB.value / 10;

// In ith iteration, setting ith significant digit of sum = sumD % 10
travB.value = travB.value % 10;

// Moving on to (i + 1)th significant digit
if(travA != null)
travA = travA.next;

if (travB.next == null){
// If carryForward > 0, Adding a node in l_b, which denotes new most significant digit of sum
// as there is no more digit to carry forward the carryForward
if (carryForward > 0) {
travB.next = new_node;
}
break;
}
travB = travB.next;
}

return l_b;
}
``````

# Add Two Numbers Solution 3: Optimal

Approach will be as similar as explained other_solution1, but this approach is optimised in terms of number of iterations and extra space used as we are storing the resultant value in one of the given two input linked list only so, we don’t require to create and allocate new linked list.

And we are not finding the longer linked list by iterating over given two linked list as we were doing in other_solution2 but when finding the resultant sum we are changing the pointer and appending the longer list’s remaining nodes to the linked list in which we are storing the resultant sum.

For more detailed explanation refer optimal_solution.

## Time Complexity

O(max(lenA, lenB)).

As we are iterating over the given linked list `l_a` and `l_b` simultaneously in one iteration. Hence complexity is maximum of length of `l_a` and length `l_b`.

## Auxiliary Space Used

O(1).

We aren’t storing anything extra and using one of the two given linked lists to store the resultant sum.

## Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(1)

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(1) + O(max(lenA, lenB)) = O(lenA + lenB).

## Code For Add Two Numbers Solution 3: Optimal

``````    /*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(max(lenA, lenB)).
* Auxiliary space: O(1).
* Total space: O(lenA + lenB).
*/

// We are storing resultant sum in l_b.
int carryForward = 0, sum = 0;
// To store carry and current sum.
// We are iterating till we reach at end of one of linkedlist.
// and update l_b with resultant sum.
while(true){
sum = l_a.value + l_b.value + carryForward;
l_b.value = sum % 10;
carryForward = sum / 10;
if(l_a.next == null || l_b.next == null){
break;
}
l_a = l_a.next;
l_b = l_b.next;
}
// If we reached the end of l_b but not of l_a, we can utilize the already created nodes
// of l_a by appending them to l_b.
if(l_a.next != null && l_b.next == null){
l_b.next = l_a.next;
}
// We iterate through remaining nodes of l_b and update it with sum of node and carry.
while(carryForward > 0 && l_b.next != null){
l_b = l_b.next;
sum = carryForward + l_b.value;
l_b.value = sum % 10;
carryForward = sum / 10;
}
// If still carry is remaining then we add extra node at tail of linkedlist l_b.
if(carryForward > 0){
l_b.next = new_node;
}
// Result will be head node of l_b (which is storing our resultant sum)
return result;
}
``````

We hope that these solutions to add two numbers problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve. Hosted By
Ryan Valles
Founder, Interview Kickstart Accelerate your Interview prep with Tier-1 tech instructors 360° courses that have helped 14,000+ tech professionals 100% money-back guarantee*

All Posts