support@artificialrace.com

Add Two Numbers Leetcode Solution in Python


Estimated reading time: 4 minutes

We’re going to be discussing Add Two Numbers Leetcode Solution in Python which is a Leetcode Medium Problem (#2).
The “Add Two Numbers” problem on LeetCode presents an interesting challenge of adding two non-negative integers represented by linked lists. The digits of these numbers are stored in reverse order, and each node in the linked list contains a single digit. The task is to perform the addition and return the result as a linked list.

Problem Statement

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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1 figure (source – leetcode)

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Leetcode Problem Link: https://leetcode.com/problems/add-two-numbers/

Solution

BruteForce Approach

Details:

Convert to Number: The linked lists are traversed to convert each digit into an integer, and the two resulting integers are summed.

Perform Addition: The sum is then converted back into a linked list, with each digit represented by a node.

Summary:

The brute force solution involves converting linked lists to integers, performing addition, and then converting the result back to a linked list.

The time complexity is dominated by the conversion steps, making it less efficient for large numbers.

Python# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next

class Solution:
def addTwoNumbersBruteForce(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
num1 = self.convert_to_number(l1)
num2 = self.convert_to_number(l2)
result = num1 + num2

return self.convert_to_linked_list(result)

def convert_to_number(self, node):
result = 0
multiplier = 1

while node:
result += node.val * multiplier
multiplier *= 10
node = node.next

return result

def convert_to_linked_list(self, number):
dummy = ListNode()
current = dummy

for digit in str(number)[::1]:
current.next = ListNode(int(digit))
current = current.next

return dummy.next

Time Complexity:

Conversion to Number: O(n) where n is the length of the longer linked list.

Conversion to Linked List: O(m) where m is the number of digits in the sum.

Optimal Approach

Details:

Two-Pointer Iteration: Similar to the better solution, two pointers traverse both linked lists simultaneously.

Perform Addition: Addition is performed digit by digit, considering any carry from the previous step.

Create Result List: The result is constructed in-place, and a new linked list is returned.

Summary:

The optimal solution shares similarities with the better solution but minimizes the use of variables and combines the addition logic with the iteration.

It maintains efficiency and handles edge cases effectively.

Pythonclass Solution:
def addTwoNumbersOptimal(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
current = dummy
carry = 0

while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0

total_sum = x + y + carry
carry, digit = divmod(total_sum, 10)

current.next = ListNode(digit)
current = current.next

if l1:
l1 = l1.next
if l2:
l2 = l2.next

return dummy.next

Time Complexity:

Iterating Through Lists: O(max(n, m)) where n and m are the lengths of the input linked lists.

So these two were the brute and optimal solutions for add two numbers leetcode problem in python. I hope you got a good understanding of the solution and will be able to solve this problem upon iterations.

Something You Might Like:

3sum Leetcode Solution in Python – Brute, Better, and Optimal.

Concurrency with Multithreading in Software Development

Sliding Window Algorithm: Explained with Example

Understanding Double Hashing: How does it work?

Asymptotic Notation in Data Structure [ Simple Explanation ]

<p>The post Add Two Numbers Leetcode Solution in Python first appeared on PyPixel.</p>


Discover more from Artificial Race!

Subscribe to get the latest posts to your email.