Two_Sum and Add_Two_Numbers

I am trying to solve some algorithm problems in Leetcode recently. I plan to write down all the solutions either written by myself or found in the internet… I want to keep track of all these solutions and plan to write an article like this weekly, and hopefully, these articles could be helpful to you, or me in the future…

In this article, I will provide the C++ implementation of two problems: “Two Sum” and “Add Two Numbers”. I will also give explanation to both of the solutions provided below.

---

---

Two Sum

Problem Statement:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

---

Solution One: Brute Force

Just a simple and brutal solution. We iterate all the possible solution using two loops, and we find whether there two numbers which sum together equal to the target number. If we find, return the two indices.

Time complexity: O(n^2)

Space complexity: O(1)

Solution Two: Hash Table

Let’s take a close look at the above code. We have noticed in the inner loop, what we want to do is compare whether the sum of two elements equals to the target. Then we can change the logic like this:

int sub = target – nums[i];

The only thing we need to compare is whether nums[j] equals to this sub, So if we want to quickly find whether an element is in a list without iterating the whole list, which data structure can we use?

Hash Table! !

The general idea here is we store the sub value as a key into a hash table, at the same time, we store the corresponding index as value of the hash table. When we want to check whether nums[j] equals to target – nums[i], we only need to test whether we can find nums[j] in our hash table. It nums[j] is there, we are done, we just return the indices of i and j.

Time Complexity: O(n)

Space Complexity: O(n)

---

---

Add Two Numbers

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 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.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

---

OK, This is what the linked list of this example look like.

This is a tricky question, try it yourself first. Basically, we need to sum each digit of an integer together and at the same time, we also need to keep an eye for the potential carry. We can safely say that the carry will not exceed 1 because the 9+9 = 18, even if we add the carry here, it is only 19, so the carry should either be 0 or 1.

Here is a brief pseudo code:

1. We define a new list node, set the pre-head pointer to it, and also set our current pointer to it.
2. We initialize our carry variable and set it to 0, we also define two pointers, p and q respectively point to the first node of linked list L1 and L2. Let’s define x is the value that p pointer could retrieve from L1, while y is retrieved from L2 via q.
3. Let’s enter our for loop now, the termination of this loop should be either p or q have reached to their end (both p and q are null) or carry is 0:
4. If p is null, which means p reaches its end, we set x = 0; if q is null, then y = 0;
5. For each iteration, we calculate the sum = x + y + carry;
6. Update the carry = sum / 10;
7. Create a new node, and make our current pointer  point to it. Store the calculated value to this node. The calculated value should be sum % 10;
8. Move p and q pointers forward respectively. Then we can safely exit the loop now.
9. Return the pre-head pointer’s next pointer.

Although it seems complex, the code is relatively simple. \^_^/

Time Complexity: O(max(m+n))    m and n are L1’s and L2’s length, respectively

Space Complexity: O(max(m+n))

What if the values in both linked lists are stored in reversed order? That’s an interesting question…

That’s all for today, thanks for reading….