Leetcode Random Challenge - Wk3 (445)

Cicero · Jul 24, 2017

Hi all,

As suggested, a separate thread per weekly challenge. This week a medium difficulty problem courtesy of the question picker:

445. Add Two Numbers II - https://leetcode.com/problems/add-two-numbers-ii/#/description

Code:
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

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

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Code:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7

How it works:

We use the random question picker, and all attempt it, one question a week.
No cheating/looking at the editorial solution until your soln is accepted on leetcode, and you're convinced you can't get it any quicker.
Language is up to you, this may help people appreciate other languages as well
Only post your time taken, language, and percentage of submissions beaten at first. Use spoiler tags for your code.

Good luck!

JSRJJ · Jul 24, 2017

code to do the same in PYTHON

Code:

# Python program to add two numbers represented by linked list

# Node class
class Node:

	# Constructor to initialize the node object
	def __init__(self, data):
		self.data = data
		self.next = None

class LinkedList:

	# Function to initialize head
	def __init__(self):
		self.head = None

	# Function to insert a new node at the beginning
	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	# Add contents of two linked lists and return the head
	# node of resultant list
	def addTwoLists(self, first, second):
		prev = None
		temp = None
		carry = 0

		# While both list exists
		while(first is not None or second is not None):

			# Calculate the value of next digit in
			# resultant list
			# The next digit is sum of following things
			# (i) Carry
			# (ii) Next digit of first list (if ther is a
			# next digit)
			# (iii) Next digit of second list ( if there
			# is a next digit)
			fdata = 0 if first is None else first.data
			sdata = 0 if second is None else second.data
			Sum = carry + fdata + sdata

			# update carry for next calculation
			carry = 1 if Sum >= 10 else 0

			# update sum if it is greater than 10
			Sum = Sum if Sum < 10 else Sum % 10

			# Create a new node with sum as data
			temp = Node(Sum)

			# if this is the first node then set it as head
			# of resultant list
			if self.head is None:
				self.head = temp
			else :
				prev.next = temp 

			# Set prev for next insertion
			prev = temp

			# Move first and second pointers to next nodes
			if first is not None:
				first = first.next
			if second is not None:
				second = second.next

		if carry > 0:
			temp.next = Node(carry)

	# Utility function to print the linked LinkedList
	def printList(self):
		temp = self.head
		while(temp):
			print temp.data,
			temp = temp.next

# Driver program to test above function
first = LinkedList()
second = LinkedList()

# Create first list
first.push(7)
first.push(2)
first.push(4)
first.push(3)
print "First List is ",
first.printList()

# Create second list
second.push(5)
second.push(6)
second.push(4)
print "\nSecond List is ",
second.printList()

# Add the two lists and see result
res = LinkedList()
res.addTwoLists(first.head, second.head)
print "\nResultant list is ",
res.printList()

Cicero · Jul 24, 2017

Chinmaya said:
/snip

Good stuff, but can you please edit your post and add spoiler and code tags to your code so its hidden? Sorry I forgot to add the 'rules' to the first post again. It just so people dont get influenced by your code.

Also, please post your time taken and percentage submissions beaten from leetcode.

Hamster · Jul 24, 2017

And put it code tags for formatting

Cicero · Jul 24, 2017

C - 25ms, 89.01% submissions beaten.

I may give it another look soon, reduce the memory usage perhaps.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
#define BUFLEN 100

int pushNumbers(int *buf, struct ListNode* root) {
    int ptr;    
    
    if (root==NULL) return 0;
    
    ptr = 0;
    while (root!=NULL) {
        buf[ptr++] = root->val;
        root = root->next;
    }
    
    return ptr;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* result;
    struct ListNode* working;
    
    int l1Stack[BUFLEN];
    int l2Stack[BUFLEN];
    int final[BUFLEN], nums, numTotal;
    int l1Ptr, l2Ptr, sum, carry;
    
    if ((l1 == NULL) && (l2 == NULL)) return NULL;
    
    l1Stack[0] = 0;
    l2Stack[0] = 0;
    
    working = (struct ListNode *)malloc(sizeof(struct ListNode));
    result = working;
    
    l1Ptr = pushNumbers(l1Stack, l1);
    l2Ptr = pushNumbers(l2Stack, l2);
    
    /* Change to read ptr's */
    if (l1Ptr) l1Ptr--;
    if (l2Ptr) l2Ptr--;
     
    carry = 0;
    
    if (l1Ptr < l2Ptr) {
        nums = l2Ptr;
    } else {
        nums = l1Ptr;
    }
    numTotal = nums;

    while ((l1Ptr>=0) && (l2Ptr>=0)) {
        sum = l2Stack[l2Ptr] + l1Stack[l1Ptr] + carry;
        final[nums--] = sum%10;
        l2Ptr--;
        l1Ptr--;
        carry = sum/10;            
    }
    
    while (l1Ptr>=0) {
        sum = l1Stack[l1Ptr] + carry;
        final[nums--] = sum%10;
        l1Ptr--;
        carry = sum/10;   
    }
    
    while (l2Ptr>=0) {
        sum = l2Stack[l2Ptr] + carry;
        final[nums--] = sum%10;
        l2Ptr--;
        carry = sum/10;   
    }
    
    if (carry) {
        working->val = carry;
        working->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        working = working->next;
    }
    
    for (nums=0; nums < numTotal; nums++) {
        working->val = final[nums];
        working->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        working = working->next;        
    }
    working->val = final[nums];    
    working->next = NULL;  

    return result;
}

JSRJJ · Jul 24, 2017

The code I have given only gives you an output of 7 0 8 7, then you need to write some piece of code to reverse the list and you will be good to go. This is not full code still

Hamster · Jul 24, 2017

Go - 29 ms, beats 50% of submissions

PHP:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	tl1 := toList(l1)
	tl2 := toList(l2)
	i1 := len(tl1) - 1
	i2 := len(tl2) - 1

	var current *ListNode

	var result int
	carry := 0
	for {
		if i1 <= -1 && i2 <= -1 {
			break
		}

		if i1 <= -1 {
			result = tl2[i2] + carry
		} else if i2 <= -1 {
			result = tl1[i1] + carry
		} else {
			result = tl1[i1] + tl2[i2] + carry
		}

		if result > 9 {
			carry = result / 10
			result = result % 10
		} else {
			carry = 0
		}

		node := &ListNode{Val: result}
		if current == nil {
			current = node
		} else {
			node.Next = current
			current = node
		}

		i1--
		i2--
	}

	if carry > 0 {
		return &ListNode{Val: carry, Next: current}
	}

	return current
}

func toList(node *ListNode) []int {
	data := []int{}
	for node != nil {
		data = append(data, node.Val)
		node = node.Next
	}
	return data
}

EDIT: Modified it to make use of channels but that just slows it down to 35ms

Cicero · Jul 24, 2017

Chinmaya said:
The code I have given only gives you an output of 7 0 8 7, then you need to write some piece of code to reverse the list and you will be good to go. This is not full code still

Haha, no issue dude. But the point is to get it accepted by leetcode, they run a whole stack of test cases on it, varying length inputs etc etc.

Post back once you've done your mods and got it accepted. Looking forward to it.

Johnatan56 · Jul 24, 2017

Cicero said:

C - 25ms, 89.01% submissions beaten.

I may give it another look soon, reduce the memory usage perhaps.

PHP:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
#define BUFLEN 100

int pushNumbers(int *buf, struct ListNode* root) {
    int ptr;    
    
    if (root==NULL) return 0;
    
    ptr = 0;
    while (root!=NULL) {
        buf[ptr++] = root->val;
        root = root->next;
    }
    
    return ptr;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* result;
    struct ListNode* working;
    
    int l1Stack[BUFLEN];
    int l2Stack[BUFLEN];
    int final[BUFLEN], nums, numTotal;
    int l1Ptr, l2Ptr, sum, carry;
    
    if ((l1 == NULL) && (l2 == NULL)) return NULL;
    
    l1Stack[0] = 0;
    l2Stack[0] = 0;
    
    working = (struct ListNode *)malloc(sizeof(struct ListNode));
    result = working;
    
    l1Ptr = pushNumbers(l1Stack, l1);
    l2Ptr = pushNumbers(l2Stack, l2);
    
    /* Change to read ptr's */
    if (l1Ptr) l1Ptr--;
    if (l2Ptr) l2Ptr--;
     
    carry = 0;
    
    if (l1Ptr < l2Ptr) {
        nums = l2Ptr;
    } else {
        nums = l1Ptr;
    }
    numTotal = nums;

    while ((l1Ptr>=0) && (l2Ptr>=0)) {
        sum = l2Stack[l2Ptr] + l1Stack[l1Ptr] + carry;
        final[nums--] = sum%10;
        l2Ptr--;
        l1Ptr--;
        carry = sum/10;            
    }
    
    while (l1Ptr>=0) {
        sum = l1Stack[l1Ptr] + carry;
        final[nums--] = sum%10;
        l1Ptr--;
        carry = sum/10;   
    }
    
    while (l2Ptr>=0) {
        sum = l2Stack[l2Ptr] + carry;
        final[nums--] = sum%10;
        l2Ptr--;
        carry = sum/10;   
    }
    
    if (carry) {
        working->val = carry;
        working->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        working = working->next;
    }
    
    for (nums=0; nums < numTotal; nums++) {
        working->val = final[nums];
        working->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        working = working->next;        
    }
    working->val = final[nums];    
    working->next = NULL;  

    return result;
}

Just testing if this works.

Yep, use PHP instead of Code, it colors it.
Hopefully I'll manage to get a chance at this before the end of the week, slightly busy currently.

Cicero · Jul 24, 2017

Hamster said:

Go - beats 50% of submissions

Code:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	tl1 := toList(l1)
	tl2 := toList(l2)
	i1 := len(tl1) - 1
	i2 := len(tl2) - 1

	var current *ListNode

	var result int
	carry := 0
	for {
		if i1 <= -1 && i2 <= -1 {
			break
		}

		if i1 <= -1 {
			result = tl2[i2] + carry
		} else if i2 <= -1 {
			result = tl1[i1] + carry
		} else {
			result = tl1[i1] + tl2[i2] + carry
		}

		if result > 9 {
			carry = result / 10
			result = result % 10
		} else {
			carry = 0
		}

		node := &ListNode{Val: result}
		if current == nil {
			current = node
		} else {
			node.Next = current
			current = node
		}

		i1--
		i2--
	}

	if carry > 0 {
		return &ListNode{Val: carry, Next: current}
	}

	return current
}

func toList(node *ListNode) []int {
	data := []int{}
	for node != nil {
		data = append(data, node.Val)
		node = node.Next
	}
	return data
}

Lekker Hamster, whats the time?

Nice to see you're always keen on these. You gonna do a Python version as well?

Hamster · Jul 24, 2017

Cicero said:
Lekker Hamster, whats the time?

Nice to see you're always keen on these. You gonna do a Python version as well?

Time is 29ms

Tried Python over lunch time (a different way) and the dam into limit crap killed me. Will try again sometime this week.

[)roi(] · Jul 25, 2017

Swift with three approaches; arrays, reversal, parent references:

Arrays: beats 82.3% of Swift submissions.

PHP:

extension Array where Element == Int
{
  func toListNode() -> ListNode
  {
    precondition(self.count > 0)
    let rootNode = ListNode(self.first!)
    var previousNode = rootNode
    for digit in self.dropFirst()
    {
      let currentNode = ListNode(digit)
      previousNode.next = currentNode
      previousNode = currentNode
    }
    return rootNode
  }
}

extension Array where Element == Int
{
  func sumWith(_ other: [Int]) -> [Int]
  {
    var (augend, addend) = self.count >= other.count ?
      (self, other) : (other, self)
    let countDiff = augend.count - addend.count
    var carry = 0
    for i in stride(from: augend.count - 1, through: 0, by: -1)
    {
      if i < countDiff && carry == 0 { break }
      let sum = i >= countDiff ?
        augend[i] + addend[i - countDiff] + carry :
        augend[i] + carry
      (augend[i], carry) = (sum % 10, sum / 10)
    }
    return carry > 0 ? [carry] + augend : augend
  }
}

extension ListNode
{
  func toArray() -> [Int]
  {
    var array = [self.val]
    var node = self.next
    while node != nil
    {
      array += [node!.val]
      node = node?.next
    }
    return array
  }
}

func +(lhs: ListNode?, rhs: ListNode?) -> ListNode?
{
  return lhs!.toArray().sumWith(rhs!.toArray()).toListNode()
}

public func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode?
{
  return l1 + l2
}

ListNode reversal: beats 100% of Swift submissions.

PHP:

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode?
{
  var (augend, addend) = (l1?.reverse(), l2?.reverse())
  let dummyNode = ListNode(0)
  var (previousNode, carry) = (dummyNode, 0)
  while augend != nil || addend != nil {
    let sum = (augend?.val ?? 0) + (addend?.val ?? 0) + carry
    carry = sum / 10
    previousNode.next = ListNode(sum % 10)
    previousNode = previousNode.next!
    augend = augend?.next
    addend = addend?.next
  }
  if carry > 0 { previousNode.next = ListNode(carry) }
  return dummyNode.next?.reverse()
}

fileprivate extension ListNode
{
  fileprivate func reverse() -> ListNode? {
    let reversalNode = ListNode(0)
    var currentNode: Optional<ListNode> = self
    while currentNode != nil {
      let temp = reversalNode.next
      reversalNode.next = ListNode(currentNode!.val)
      reversalNode.next?.next = temp
      currentNode = currentNode?.next
    }
    return reversalNode.next
  }
}

Build ListNode parent references; in place update of largest ListNode: beats 92.4% of Swift submissions.

PHP:

extension ListNode
{
  convenience init(_ value: Int, _ node: ListNode?)
  {
    self.init(value)
    self.next = node
  }
}

extension ListNode
{
  func getReferences() -> [(child: ListNode, parent: ListNode?)]
  {
    var references = [(self, Optional<ListNode>.none)]
    var (child, parent) = (self.next, self)
    while child != nil
    {
      references.append((child!, parent))
      (parent, child) = (child!, child?.next)
    }
    return references
  }
}

extension ListNode
{
  func sumWith(_ other: ListNode?) -> ListNode?
  {
    let a = self.getReferences()
    guard let b = other?.getReferences() else { return self }
    var (augend, addend) = a.count >= b.count ? (a, b) : (b, a)
    let countDiff = augend.count - addend.count
    var carry = 0
    for i in stride(from: augend.count - 1, through: 0, by: -1)
    {
      if i < countDiff && carry == 0 { break }
      let sum = i >= countDiff ?
        augend[i].child.val + addend[i - countDiff].child.val + carry :
        augend[i].child.val + carry
      (augend[i].child.val, carry) = (sum % 10, sum / 10)
    }
    return carry > 0 ? ListNode(carry, augend[0].child) : augend[0].child
  }
}

func +(lhs: ListNode?, rhs: ListNode?) -> ListNode?
{
  return lhs?.sumWith(rhs)
}

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode?
{
  return l1 + l2
}

Again I'm ignoring the leet times as these serve only to confirm leet's poor Swift compiler optimisation. On the leet site the second algorithm using ListNode reversal is the fastest, but locally the array based algorithm is far more optimisable by SIL && LLVM.
Local times as example; the runtimes for the arrays algorithm run ~8ms local vs. ~20ms for the ListNode reversal using a similar 1563 test dataset.

Notes:
Unfortunately leet dictated the type definition for the ListNode; i.e. constructed with reference semantics (class) and no weak parent reference; which would have made in place addition much simpler, for example:

PHP:

public class ListNode<T> 
{
   var value: T
   var next: ListNode?
   weak var previous: ListNode?
}

Alternative would be to use a recursive enum value type for this, for example:

PHP:

public enum ListNode<T> {
  indirect case node(T, next: ListNode<T>)
  case end
}

The recursive code to deal with ListNode or Tree like structures tends to be quite concise and fast; except being a value type; any modification would result in a new copy being created, which can be avoided with reference semantics (especially with a weak parent reference).

Hamster · Jul 25, 2017

And the same solution in Python:

129ms, beats 67.4% of Python submissions

PHP:

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        list1 = self.toList(l1)
        list2 = self.toList(l2)
        i1 = len(list1) - 1
        i2 = len(list2) - 1

        current = None
        result = 0
        carry = 0

        while True:
            if i1 <= -1 and i2 <= -1:
                break
            elif i1 <= -1:
                result = list2[i2] + carry
            elif i2 <= -1:
                result = list1[i1] + carry
            else:
                result = list1[i1] + list2[i2] + carry

            if result > 9:
                carry = result / 10
                result = result % 10
            else:
                carry = 0

            node = ListNode(result)
            if current is None:
                current = node
            else:
                node.next = current
                current = node

            i1 -= 1
            i2 -= 1

        if carry > 0:
            node = ListNode(carry)
            node.next = current
            return node

        return current

    def toList(self, node):
        data = []
        while node != None:
            data.append(node.val)
            node = node.next
        return data

Cicero · Jul 27, 2017

Our times so far, hoping for some more submissions in the next few days.

@Chinmaya came close, should easily be able to adapt his submission and post a time
@Johnatan56 hoping he finds some spare time as well

445) Add Two Numbers II
C

Cicero - 25ms, beats 89.01%

Go

Hamster - 29 ms, beats 50%

Swift

[)roi(] - best leetcode submission - beats 100%

Python

Hamster - 129ms, beats 67.4%

[)roi(] · Jul 27, 2017

Cicero said:
Our times so far, hoping for some more submissions in the next few days.

@Chinmaya came close, should easily be able to adapt his submission and post a time
@Johnatan56 hoping he finds some spare time as well

445) Add Two Numbers II
C

Cicero - 25ms, beats 89.01%

Go

Hamster - 29 ms, beats 50%

Swift

[)roi(] - best leetcode submission - beats 100%

Python

Hamster - 129ms, beats 67.4%

Cool, but practically my submission is only a "best Swift". Plus your C approach and Hamster's Python / Go code utilised the exact same approach as my Swift array version (great minds and all of that)

Cicero · Jul 27, 2017

[)roi(];20123245 said:
Cool, but practically my submission is only a "best Swift". Plus your C approach and Hamster's Python / Go code utilised the exact same approach as my Swift array version (great minds and all of that)

That's why I list them by language.

You need to coerce one of your Swift colleagues to join. Although I think you've reached 100% on every Swift submission for each challenge, so they may get slightly discouraged by that, haha.

Hamster · Jul 27, 2017

[)roi(];20123245 said:
Cool, but practically my submission is only a "best Swift". Plus your C approach and Hamster's Python / Go code utilised the exact same approach as my Swift array version (great minds and all of that)

You should really post the times speed can get a general idea of Swift's speed. Can't be as bad as Python

[)roi(] · Jul 27, 2017

Hamster said:
You should really post the times speed can get a general idea of Swift's speed. Can't be as bad as Python

it's pointless because leet applies none of the optimizations. As example of how bad it is; to achieve 100% with this challenge required me to do a pointless micro optimization with access control; explicitly add "fileprivate" instead of the default internal access, made a 62% into 100%; this is a pointless code optimization, because the default release compiler settings level this.

Plus there's many Swift vs. X language comparisons; which in practice performs on par with C, C++, Rust, ... Also Swift's a young language, so the current priority is on extending the compiler's language features rather than optimizations.

Hamster · Jul 28, 2017

[)roi(];20124007 said:
it's pointless because leet applies none of the optimizations. As example of how bad it is; to achieve 100% with this challenge required me to do a pointless micro optimization with access control; explicitly add "fileprivate" instead of the default internal access, made a 62% into 100%; this is a pointless code optimization, because the default release compiler settings level this.

Plus there's many Swift vs. X language comparisons; which in practice performs on par with C, C++, Rust, ... Also Swift's a young language, so the current priority is on extending the compiler's language features rather than optimizations.

Yes yes, all that...but it's still fun to see

Cicero · Jul 28, 2017

[(roi(], maybe pop the leetcode guys a suggestion email as well? Maybe they're just as Swift clueless as I am?

Join the MyBroadband community

Get started

Leetcode Random Challenge - Wk3 (445)

Expert Member

Well-Known Member

Expert Member

Resident Rodent

Expert Member

Well-Known Member

Resident Rodent

Expert Member

Honorary Master

Expert Member

Resident Rodent

Executive Member

Resident Rodent

Expert Member

Executive Member

Expert Member

Resident Rodent

Executive Member

Resident Rodent

Expert Member