LeetCode Go #2. Add Two Numbers

coderazade — Sat, 15 Jul 2023 10:17:42 +0000

Problem Description

You can find the problem on Leetcode.

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.

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]

Understand Problem

We are given two linked lists representing non-negative integers. The digits are stored in reverse order, meaning the units digit is at the head of the list. We need to add the two numbers and return the result as a new linked list.

Implementation

Let's implement the solution in Go.

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    curr := dummyHead
    carry := 0

    for l1 != nil || l2 != nil {
        sum := carry

        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }

        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }

        curr.Next = &ListNode{Val: sum % 10}
        curr = curr.Next
        carry = sum / 10
    }

    if carry > 0 {
        curr.Next = &ListNode{Val: carry}
    }

    return dummyHead.Next
}

Testing

Let's write some tests to verify that our implementation is correct.

package main

import (
    "reflect"
    "testing"
)

func buildLinkedList(nums []int) *ListNode {
    dummyHead := &ListNode{}
    curr := dummyHead

    for _, num := range nums {
        curr.Next = &ListNode{Val: num}
        curr = curr.Next
    }

    return dummyHead.Next
}

func getListValues(head *ListNode) []int {
    values := make([]int, 0)

    for head != nil {
        values = append(values, head.Val)
        head = head.Next
    }

    return values
}

func TestAddTwoNumbers(t *testing.T) {
    tests := []struct {
        l1   []int
        l2   []int
        want []int
    }{
        {[]int{2, 4, 3}, []int{5, 6, 4}, []int{7, 0, 8}},
        {[]int{0}, []int{0}, []int{0}},
        {[]int{9, 9, 9, 9, 9, 9, 9}, []int{9, 9, 9, 9}, []int{8, 9, 9, 9, 0, 0, 0, 1}},
    }

    for _, test := range tests {
        l1 := buildLinkedList(test.l1)
        l2 := buildLinkedList(test.l2)
        got := getListValues(addTwoNumbers(l1, l2))

        if !reflect.DeepEqual(got, test.want) {
            t.Errorf("Input: l1=%v, l2=%v\nGot: %v\nWant: %v", test.l1, test.l2, got, test.want)
        }
    }
}

Conclusion

Well done! You have successfully solved the Add Two Numbers problem on Leetcode. This problem introduced you to arithmetic operations on linked lists. By reversing the order of digits, you were able to perform addition on the linked lists and return the result as a new linked list.

Now that you have gained confidence in solving this problem, it's time to tackle more challenges on Leetcode. Keep practicing and enhancing your problem-solving skills. Good luck with your future endeavors!

LeetCode Go #1. Two sum

coderazade — Sat, 15 Jul 2023 10:16:52 +0000

Problem Description

You can find the problem on Leetcode.

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: The sum of 2 and 7 is 9. Therefore, the indices of the two numbers are 0 and 1.

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Understand Problem

We are given an array of integers and a target value. Our task is to find two numbers in the array that add up to the target value. We need to return the indices of these two numbers.

Implementation

Let's implement the solution in Go.

package main

func twoSum(nums []int, target int) []int {
    complements := make(map[int]int)

    for i, num := range nums {
        complement := target - num
        if index, found := complements[complement]; found {
            return []int{index, i}
        }
        complements[num] = i
    }

    return nil
}

Testing

To test the solution, we can use the testing package in Go. We'll write multiple test cases to ensure our implementation works as expected.

package main

import (
    "reflect"
    "testing"
)

func TestTwoSum(t *testing.T) {
    tests := []struct {
        nums   []int
        target int
        want   []int
    }{
        {[]int{2, 7, 11, 15}, 9, []int{0, 1}},
        {[]int{3, 2, 4}, 6, []int{1, 2}},
        {[]int{3, 3}, 6, []int{0, 1}},
    }

    for _, test := range tests {
        got := twoSum(test.nums, test.target)
        if !reflect.DeepEqual(got, test.want) {
            t.Errorf("Input: nums=%v, target=%d\nGot: %v\nWant: %v", test.nums, test.target, got, test.want)
        }
    }
}

Conclusion

Congratulations! You have successfully solved the Two Sum problem on Leetcode. By solving this problem, you have learned how to find two numbers in an array that add up to a specific target value. This problem is a classic example of using a map (or dictionary) to store complements and perform efficient lookups.

Now that you are familiar with solving this problem, you can move on to the next challenges on Leetcode and continue improving your problem-solving skills. Good luck!

DEV Community: coderazade

LeetCode Go #2. Add Two Numbers

Problem Description

Example 1:

Example 2:

Example 3:

Understand Problem

Implementation

Testing

Conclusion

LeetCode Go #1. Two sum

Problem Description

Example 1:

Example 2:

Example 3:

Understand Problem

Implementation

Testing

Conclusion