8000 P-2-Add-Two-Numbers · aditya-2k23/Leetcode@085e00b · GitHub
[go: up one dir, main page]
Skip to content

Commit 085e00b

Browse files
aditya-2k23aditya-2k23
committed
P-2-Add-Two-Numbers
Introduces implementations in C++, Python, and Java for solving the "Add Two Numbers" problem from LeetCode. Provides iterative, recursive, and integer-conversion approaches, with complexity analysis and constraints. Includes detailed README, test cases, and instructions for running tests in all supported languages.
1 parent f4af821 commit 085e00b

File tree

8 files changed

+501
-2
lines changed

8 files changed

+501
-2
lines changed

‎README.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
[![GitHub](https://img.shields.io/badge/Repository-blue?logo=github)](https://github.com/aditya-2k23/leetcode)
44
[![License](https://img.shields.io/badge/LICENSE-MIT-yellow?logo=license.svg)](https://github.com/aditya-2k23/leetcode/blob/main/LICENSE)
5-
![Problems Solved](https://img.shields.io/badge/Solved-20-brightgreen) <!-- Update this count as you solve more problems -->
5+
![Problems Solved](https://img.shields.io/badge/Solved-21-brightgreen) <!-- Update this count as you solve more problems -->
66
![Language](https://img.shields.io/badge/Language-Python%20%7C%20Java%20%7C%20C++-orange)
77
[![Wiki](https://img.shields.io/badge/Wiki-Available-blueviolet)](https://github.com/aditya-2k23/leetcode/wiki)
88
[![Discussions](https://img.shields.io/badge/Discussions-Open-blue)](https://github.com/aditya-2k23/leetcode/discussions)
@@ -20,6 +20,7 @@ Or
2020
Below is a list of problems solved in this repository:
2121

2222
- [Problem 1: Two Sum](problems/P-1-two-sum)
23+
- [Problem 2: Add Two Numbers](problems/P-2-add-two-numbers)
2324
- [Problem 7: Reverse Integer](problems/P-7-reverse-integer)
2425
- [Problem 8: String to Integer (atoi)](problems/P-8-string-to-integer-(atoi))
2526
- [Problem 9: Palindrome Number](problems/P-9-palindrome-number)
@@ -107,4 +108,4 @@ This project is licensed under the MIT License. See the [LICENSE](LICENSE) file
107108

108109
Happy coding! 🚀
109110

110-
> _Last updated: June 20, 2025_
111+
> _Last updated: June 22, 2025_

‎problems/P-2-add-two-numbers/README.md

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
# Problem 2: Add Two Numbers
2+
3+
- **Difficulty**: Medium
4+
- **Topics**: Linked List, Math, Recursion
5+
- **LeetCode Link**: [Problem URL](https://leetcode.com/problems/add-two-numbers/)
6+
7+
## Problem Description
8+
9+
You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order**, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
10+
11+
You may assume the two numbers do not contain any leading zero, except the number `0` itself.
12+
13+
**Example 1:**
14+
15+
![img](https://assets.leetcode.com/uploads/2020/10/02/addtwonumber1.jpg)
16+
17+
> Input: l1 = [2,4,3], l2 = [5,6,4]
18+
> Output: [7,0,8]
19+
> Explanation: 342 + 465 = 807.
20+
21+
**Example 2:**
22+
23+
> Input: l1 = [0], l2 = [0]
24+
> Output: [0]
25+
26+
**Example 3:**
27+
28+
> Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
29+
> Output: [8,9,9,9,0,0,0,1]
30+
31+
**Constraints:**
32+
33+
- The number of nodes in each linked list is in the range `[1, 100]`.
34+
- `0 <= Node.val <= 9`
35+
- It is guaranteed that the list represents a number that does not have leading zeros.
36+
37+
## Approach
38+
39+
So, there are total of three approaches to solve this problem:
40+
41+
### **Iterative Approach**: Traverse both linked lists, adding corresponding digits and managing carry
42+
43+
#### Steps
44+
45+
1. Add the values of the nodes one by one in a `sum` variable.
46+
2. Set the carry for the next iteration as `sum // 10`.
47+
3. Create a new node with the value `sum % 10` and link it to the result list.
48+
4. Move to the next nodes in both linked lists.
49+
5. Continue until both linked lists are fully traversed and there is no carry left.
50+
6. If there is a carry left after the last addition, create a new node with that carry value.
51+
7. Return the head of the result linked list.
52+
53+
### **Recursive Approach**: Use recursion to add corresponding digits and handle carry
54+
55+
#### Steps
56+
57+
1. Define a recursive function that takes two nodes and a carry as parameters.
58+
2. If both nodes are null and carry is 0, return null.
59+
3. Then calculate the sum of the values of the nodes and the carry.
60+
4. Create a new node with the value `sum % 10`.
61+
5. Set the carry for the next recursive call as `sum // 10`.
62+
6. Call the recursive function for the next nodes in both linked lists, passing the carry.
63+
7. Link the new node to the result of the recursive call.
64+
8. Return the new node as the head of the result linked list.
65+
66+
### **Convert to Integer**: Convert both linked lists to integers, add them, and convert the result back to a linked list
67+
68+
- _(But this won't work for large numbers due to integer overflow. So, we can't use this approach in LeetCode.)_
69+
70+
#### Steps
71+
72+
1. Traverse both linked lists to convert them into integers.
73+
2. Add the two integers.
74+
3. Convert the sum back into a linked list.
75+
4. Return the head of the new linked list.
76+
77+
## Solution
78+
79+
- **Language**: C++ (Iterative Approach)
80+
- **File**: [solution.cpp](solution.cpp)
81+
82+
##
83+
84+
- **Language**: Python (Recursive Approach)
85+
- **File**: [solution.py](solution.py)
86+
87+
##
88+
89+
- **Language**: Java (Convert to Integer Approach) _Not recommended for large numbers_
90+
- **File**: [solution.java](solution.java)
91+
92+
## Notes
93+
94+
- The iterative approach is generally preferred for this problem due to its efficiency and simplicity.
95+
- The recursive approach is elegant but may lead to stack overflow for very long linked lists.
96+
97+
### Complexity Analysis
98+
99+
- **Time Complexity**:
100+
- **Iterative Approach**: O(max(m, n)), where m and n are the lengths of the two linked lists.
101+
- **Recursive Approach**: O(max(m, n)), where m and n are the lengths of the two linked lists.
102+
- **Convert to Integer Approach**: O(m + n), where m and n are the lengths of the two linked lists.
103+
- **Space Complexity**:
104+
- **Iterative Approach**: O(max(m, n)), for the result linked list.
105+
- **Recursive Approach**: O(max(m, n)), for the recursion stack.
106+
- **Convert to Integer Approach**: O(1), if we ignore the space used for the result linked list.
107+
108+
## Test Cases
109+
110+
See the [`tests`](/tests/) directory for test cases in different languages.
111+
112+
- **C++**: [test.cpp](tests/test.cpp)
113+
- **Python**: [test.py](tests/test.py)
114+
- **Java**: [test.java](tests/test.java)
115+
- **Test Cases**: The test cases cover various scenarios including:
116+
- Basic addition of two numbers.
117+
- Handling of carry in the addition.
118+
- Edge cases like adding zeros.
119+
- Large numbers represented by linked lists.
120+
121+
### Running Tests
122+
123+
- **C++ (Simple)**: `cd tests; g++ test.cpp ../solution.cpp -o test; ./test`
124+
- **Python**: `cd tests; python test.py`
125+
- **Java**: `javac .\solution.java tests/test.java; java -cp ".;tests" test`
126+
127+
---
128+
129+
> **Solved on**: 21/06/2025 |
130+
> **Time taken**: 00:23:05 |
131+
> **Attempts**: 5

‎problems/P-2-add-two-numbers/solution.cpp

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/*
2+
* LeetCode Problem: 2. Add Two Numbers
3+
* Difficulty: Medium
4+
* Topics: Linked List, Math, Recursion
5+
* Date Solved: 21/06/2025
6+
*/
7+
8+
#include <bits/stdc++.h>
9+
using namespace std;
10+
11+
struct ListNode {
12+
int val;
13+
ListNode* next;
14+
ListNode(int x) : val(x), next(nullptr) {}
15+
};
16+
17+
class Solution {
18+
public:
19+
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
20+
ListNode* head = new ListNode(0);
21+
ListNode* temp = head;
22+
23+
int carry = 0;
24+
while (l1 || l2 || carry) {
25+
int sum = carry;
26+
27+
if (l1) {
28+
sum += l1->val;
29+
l1 = l1->next;
30+
}
31+
if (l2) {
32+
sum += l2->val;
33+
l2 = l2->next;
34+
}
35+
36+
carry = sum / 10;
37+
temp->next = new ListNode(sum % 10);
38+
temp = temp->next;
39+
}
40+
41+
return head->next;
42+
}
43+
};

‎problems/P-2-add-two-numbers/solution.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/*
2+
* LeetCode Problem: 2. Add Two Numbers
3+
* Difficulty: Medium
4+
* Topics: Linked List, Math, Recursion
5+
* Date Solved: 21/06/2025
6+
*/
7+
8+
class ListNode {
9+
long val;
10+
ListNode next;
11+
12+
ListNode(long x) {
13+
val = x;
14+
}
15+
}
16+
17+
public class solution {
18+
private long toNumber(ListNode l) {
19+
long num = 0;
20+
long place = 1;
21+
22+
while (l != null) {
23+
num += l.val * place;
24+
place *= 10;
25+
l = l.next;
26+
}
27+
28+
return num;
29+
}
30+
31+
private ListNode toList(long num) {
32+
if (num == 0)
33+
return new ListNode(0);
34+
35+
ListNode head = new ListNode(0);
36+
ListNode temp = head;
37+
38+
while (num > 0) {
39+
temp.next = new ListNode(num % 10);
40+
num /= 10;
41+
temp = temp.next;
42+
}
43+
44+
return head.next;
45+
}
46+
47+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
48+
return toList(toNumber(l1) + toNumber(l2));
49+
}
50+
}

‎problems/P-2-add-two-numbers/solution.py

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
"""
2+
LeetCode Problem: 2. Add Two Numbers
3+
Difficulty: Medium
4+
Topics: Linked List, Math, Recursion
5+
Date Solved: 21/06/2025
6+
"""
7+
8+
from typing import Optional
9+
10+
class ListNode:
11+
def __init__(self, val=0, next=None):
12+
self.val = val
13+
self.next = next
14+
15+
class Solution:
16+
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry: int = 0) -> Optional[ListNode]:
17+
if not l1 and not l2 and carry == 0:
18+
return None
19+
20+
sum = carry
21+
22+
if l1:
23+
sum += l1.val
24+
l1 = l1.next
25+
if l2:
26+
sum += l2.val
27+
l2 = l2.next
28+
29+
carry = sum // 10
30+
node = ListNode(sum % 10)
31+
node.next = self.addTwoNumbers(l1, l2, carry)
32+
33+
return node

‎problems/P-2-add-two-numbers/tests/test.cpp

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
#include "../solution.cpp"
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
// Helper to create a linked list from a vector
6+
ListNode* createList(const vector<int>& vals) {
7+
if (vals.empty()) return nullptr;
8+
ListNode* head = new ListNode(vals[0]);
9+
ListNode* curr = head;
10+
for (size_t i = 1; i < vals.size(); ++i) {
11+
curr->next = new ListNode(vals[i]);
12+
curr = curr->next;
13+
}
14+
return head;
15+
}
16+
17+
// Helper to convert linked list to vector
18+
vector<int> toVector(ListNode* head) {
19+
vector<int> res;
20+
while (head) {
21+
res.push_back(head->val);
22+
head = head->next;
23+
}
24+
return res;
25+
}
26+
27+
// Helper to free linked list
28+
void freeList(ListNode* head) {
29+
while (head) {
30+
ListNode* tmp = head;
31+
head = head->next;
32+
delete tmp;
33+
}
34+
}
35+
36+
bool testFunction(const vector<int>& l1, const vector<int>& l2, const vector<int>& expected, int testNumber) {
37+
Solution sol;
38+
ListNode* list1 = createList(l1);
39+
ListNode* list2 = createList(l2);
40+
ListNode* result = sol.addTwoNumbers(list1, list2);
41+
vector<int> resultVec = toVector(result);
42+
cout << "Test Case " << testNumber << ": ";
43+
cout << "Input1: [";
44+
for (size_t i = 0; i < l1.size(); ++i) { cout << l1[i]; if (i < l1.size() - 1) cout << ","; }
45+
cout << "] Input2: [";
46+
for (size_t i = 0; i < l2.size(); ++i) { cout << l2[i]; if (i < l2.size() - 1) cout << ","; }
47+
cout << "] ";
48+
if (resultVec == expected) {
49+
cout << "Passed\n";
50+
freeList(list1); freeList(list2); freeList(result);
51+
return true;
52+
}
53+
else {
54+
cout << "Failed: Expected [";
55+
for (size_t i = 0; i < expected.size(); ++i) { cout << expected[i]; if (i < expected.size() - 1) cout << ","; }
56+
cout << "], Got [";
57+
for (size_t i = 0; i < resultVec.size(); ++i) { cout << resultVec[i]; if (i < resultVec.size() - 1) cout << ","; }
58+
cout << "]\n";
59+
freeList(list1); freeList(list2); freeList(result);
60+
return false;
61+
}
62+
}
63+
64+
void runTests() {
65+
int passed = 0, total = 0;
66+
if (testFunction({ 2,4,3 }, { 5,6,4 }, { 7,0,8 }, ++total)) passed++; // 342+465=807
67+
if (testFunction({ 0 }, { 0 }, { 0 }, ++total)) passed++;
68+
if (testFunction({ 9,9,9,9,9,9,9 }, { 9,9,9,9 }, { 8,9,9,9,0,0,0,1 }, ++total)) passed++; // 9999999+9999=10009998
69+
if (testFunction({ 1,8 }, { 0 }, { 1,8 }, ++total)) passed++;
70+
if (testFunction({ 5 }, { 5 }, { 0,1 }, ++total)) passed++; // 5+5=10
71+
if (testFunction({ 1 }, { 9,9,9 }, { 0,0,0,1 }, ++total)) passed++; // 1+999=1000
72+
if (testFunction({ 9,9,9 }, { 1 }, { 0,0,0,1 }, ++total)) passed++; // 999+1=1000
73+
if (testFunction({ 2,4,9 }, { 5,6,4,9 }, { 7,0,4,0,1 }, ++total)) passed++; // 942+9465=10407
74+
if (testFunction({ 0,1 }, { 0,1,2 }, { 0,2,2 }, ++total)) passed++; // 10+210=220
75+
if (testFunction({ 9,9 }, { 1 }, { 0,0,1 }, ++total)) passed++; // 99+1=100
76+
if (testFunction({ 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 }, { 5,6,4 }, { 6,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 }, ++total)) passed++; // Large numbers
77+
cout << "\nTest Results: " << passed << "/" << total << " passed.\n";
78+
if (passed == total) cout << "All tests passed!\n";
79+
else cout << "Some tests failed.\n";
80+
}
81+
82+
int main() {
83+
runTests();
84+
return 0;
85+
}

0 commit comments

Comments
 (0)
0