Multiply Strings

Hello everyone!

Today we will be going over another LeetCode problem: "Multiplying Strings." This problem will have a solution similar to that of "Add Two Numbers." As always, the source code will be at the end of the post. Without further adieu, lets get right into it!

Multiply Strings

This medium difficulty problem asks us to multiply two strings:

The prompt also tells us that the lengths of the given strings can go up to 109 characters, the strings contains only digits (so we do not need to worry about numbers in word form), the strings do not contain leading zeros (like 0100 instead of 100), and we cannot libraries that can do the conversions for us.

Solution

At the beginning, I had an idea to use base 10 and the digits provided in the string to essentially translate the string version of the number into an integer. So if one of the strings is "2101", we can use the digits provided to make the follow conversion: "2101" -> 2000 + 100 + 1 = 2101 (int). The issue with this solution is that the strings may have up to 109 digits, which means we cannot store it in the primitive C++ integer. So this solution is a no go.

A work around for this is similar to that of "Add Two Numbers." I created a vector representation of the number within the string and used the vectors to conduct the multiplication. In the multiplication, I had to consider the carry just like in "Add Two Numbers" (which I inadvertently called "extra" in the source code). I also ported over the addition code from my "Add Two Numbers" solution, as a part of long multiplication is the addition at the end:

When I was testing my code before submitting, I ran into a bug where my answer will report 1 leading zero:

The bug is located within my multiply_vector helper method, where I was pushing back the "remainder" and "extra" in my "sum" vector before completing the iteration of the outer loop. What I ended up doing was add some code to remove the leading zero when converting the result vector into a string. This ended up causing me to fail a test of 0 * 0, as the result will be zero and it will be filtered out when processing the result string.

This bug however made me realize that I can go through some multiplications rather quickly. One case would be if one of the given numbers is 0. If the number is 0, then I will return a string "0" as 0 times anything is 0. Another case will be if one of the given numbers is 1. If one of the numbers is 1, I return the other number given because 1 times x is x.

Results

The run time for this problem is significantly slower than the other problems I have done. One reason would probably be the double loops I use to conduct the multiplication. Another thing would be the conversion of the strings to vectors before doing the multiplication, as strings could go up to 109 characters as mentioned. What I could have done was use the given strings themselves for the multiplication rather than converting them to vectors.

Conclusion

Overall, this was a pretty interesting problem to solve. It was similar to "Add Two Numbers" in the sense that it involves converting some data into a form that is usable for processing and calculations. Thank you all for reading and I will see you next time!

Link to source code: https://github.com/EricFlorin/Leetcode-Solutions/blob/master/Multiply%20Strings.cpp

Find First and Last Position of Element in Sorted Array

Hello everyone,

Today we will be going over another LeetCode problem: "Find First and Last Position of Element in Sorted Array." As always, source code is at the end of the post. Without further adieu, lets get right into it!

Find First and Last Position of Element in Sorted Array

The problem is asking us to return a vector<int> with the position of the first and last occurrence of a given target value:

There is a time complexity requirement of O(log N). If there is no occurrence of the target value, we return a vector<int> containing [-1, -1].

Solution

We know that the vector is sorted in ascending order and that the run time complexity must be O(log N).

We can achieve the O(log N) time complexity by using the binary search algorithm. Binary search will allow us to find at least one occurrence of the target value and also tell us if the target does not exist within the array.

The issue with binary search is that it gives the position of the first occurrence of the target it finds. That means that the position it gives is not necessarily the very first or last occurrence of the target, as shown in the image below:

To solve this, we will be using "The Battleship" method. "Battleship" is a board game where you try to sink all of your opponent's ships. The thing is that the locations of those ships are unknown to you because of a barrier between you and your opponent. A common tactic used in the game is to first figure out the location of an opponent's ships by guessing random locations. Once you hit one of your opponent's ships, you start attacking locations in proximity of the first hit. You keep doing this until you sink the ship:

In our case, the result from the binary search is our "first hit". Starting at the location given by the binary search, we do a proximal check to determine where are the first and last occurrence of the target.

Results

The results were pretty good. I don't really have much to say about them. One thing though is that I wonder how some people made solutions that are faster than 4 ms based on distribution graphs.

Another is that I was looking through the official solutions for this problem, and I was surprised that one of them was a linear search solution. I may submit a linear search solution to see if it will be accepted, since the problem asked for a O(log N) solution, not an O(N) solution.

Conclusion

Overall, this was a pretty good problem. I am currently looking for a new problem, so it will be a while until I post again. Until then, thank you for reading!

Link to source code: https://github.com/EricFlorin/Leetcode-Solutions/blob/master/Find%20First%20and%20Last%20Position%20of%20Element%20in%20Sorted%20Array.cpp

Leetcode Problem: "pow(x, n)"

Hello everyone,

Sorry for the long wait for this post; recently I started helping my C++ professor debug a few labs and I was having issues of my own with today's problem. Today we will be going over the "pow(x, n)" Leetcode problem. This problem is a medium difficulty problem, though the description makes it seem it is simpler than what it actually is. At the end of the post I have attached my solution code for this problem. Without further ado, lets get right into this!

pow(x, n)

From the prompt and what we know about exponents, we know a few things:

1. The range of x
2. n is an integer and its range
3. Things about exponents
1. x raised to 0 gives us 1
2. x raised to 1 gives us x
3. x raised to -1 gives us (1 / x)

One important thing to remember is that n could be the maximum or minimum number in its range.

Solution

The first solution that I started out was a "loop" solution. I have an if-else chain that covers the basics of powers (like x^0 = 1) and executes the correct for-loop depending on if n was positive or negative. If n was positive, the for-loop will calculate the power by multiplying the base, x, by itself n times. If n was negative, the for-loop will calculate the power of the denominator first, then return (1 / denominator) because 1 to the power of anything is always 1 (see code).

However, I ran into a time limit issue:

My code was too slow to pass test cases involving large exponents. The reason for it is that the loops causes the worst-case time complexity to be O(n), where n is dependent on the exponent. Since n, in this test case, was set to the maximum number in its range, it will take a while to calculate.

I ended up looking up the worst-case time complexity that I must achieve for my implementation of pow(x, n). The prompt did not state the speed I should aim for, so I researched into the ideal time complexity for pow(x, n).

One post I saw on StackOverflow stated that pow(x, n) needed a constant time complexity:

However, the solution for this (as shown above) is currently out of the realm of what I know so far. Mainly because of I do not know how 2 XOR (y*log2(x)) gives the correct results.

After digging a little further, I ended up using a solution given by geeksforgeeks.org:

This solution uses recursion to do the power calculations. This solution is O(log N) because we are dividing the problem by (y / 2) with each call to power(x, y). At first I was wondering how this solution could work, until I remember that we can split powers and still get the same result.

x^n = x^(n / 2) * x^(n / 2) = x^(n / 4) * x^(n / 4) * x^(n / 4) * x^(n / 4) = … (when n is even)

x^n = x * x^(n / 2) * x^(n / 2) = x * x^(n / 4) * x^(n / 4) * x^(n / 4) * x^(n / 4) = … (when n is odd)

I did not use the exact code as shown above, as this code takes into account the fact that y can be positive or negative. In my solution, it firsts makes the necessary checks in myPow(x, n), then calls myPowRecur(x, n) when needed. myPowRecur(x, n) assumes n will be a positive integer because myPow(x, n) makes n positive before calling myPowRecur(x, n) when n is negative.

Results

After a few bug fixes and tests, I manage to pass Leetcode's tests:

Run time is pretty low due to the O(log N) recursive solution. The memory usage comes from our use of variables and the recursive method calls on the stack.

Conclusion

Overall, this was a pretty hard problem to solve. When I first saw the "medium" difficulty rating after reading the prompt, I though this problem should have been rated as "easy". However, I soon saw that this was no easy problem, especially since I took the geeksforgeeks.org solution and modified it to my means. Nevertheless, it was quite enjoyable to solve and such. I will be working on another Leetcode problem soon. Thank you for reading and I will see you next time!

Link to source: https://github.com/EricFlorin/Leetcode-Solutions/blob/master/Pow(x%2C%20n).cpp

Introductory and "Add Two Numbers"

Hello everyone,

Welcome to my new blog! I am starting this blog to be a personal portfolio of things relating to CS: personal projects, information on different data structures and algorithms, LeetCode problems, and more!

Today, I will be going through a LeetCode problem called "Add Two Numbers." I started another blog for a CS class I was taking, but I am still relatively new to blogging so most posts may not flow that well. For these LeetCode problem posts, I will include a link to my solution it at the end of the post. Without further ado, lets get right into it!

Add Two Number

"Add Two Numbers" is a medium difficulty LeetCode problem. The prompt states the following:

We need a implement the addTwoNumbers(ListNode* l1, ListNode* l2) to add two numbers, represented by linked lists, and return the sum, also represented by a linked list. From the prompt, we know a few things:

1. The given linked lists contain at least one number.
2. The number represented in the linked list are non-negative (unsigned)
3. The digits are in reverse order.

What we do not know are the maximum length of the linked lists and if the linked lists have the same size.

Possible Solutions

I came up with two possible solutions to the problem:

1. Turn the linked lists into strings, then turn the strings into integers to conduct addition. After doing the addition, turn the sum integer into a string and then into our "result" linked list and return it.
2. Add the numbers directly using the given linked lists.

I first started with Solution #1 because I wanted to avoid interacting with the linked lists as much as possible. It also allows me to ignore the size of the linked lists, as the linked lists will become integers before the addition. However, there is a lot of conversions.

However, Solution #1 does not work because some of the numbers that the linked lists represent require more than 8 bytes to be stores, and 8 bytes is the size of an int. I discovered this after I got an std::out_of_range exception when I was using std::stoul() to convert my strings into an unsigned long.

I ended up having to implement Solution #2. However, it was tricky to implement:

1. I can get two linked lists of unequal length.
2. When adding two numbers I get a sum that is greater than or equal to 10.
3. The linked lists I had to use in the implementation are created through a struct called ListNode. What this means is that I will be dealing with ListNode pointers, which makes things more trickier.

To solve Issue #1, I created a method, called "preprocessLists", to make the two lists be the same size. I also created another method, called "addNumberToList", to add an int to a given linked list. The "addNumberToList" method returns a pointer to the newly added node to make it easier to use iterators and double-pointers in "preprocessLists". The side effect of "preprocessLists" is that it makes changes to the original list. I was unsure at the time of whether to not I should modify the original list, as I was told not to unless otherwise specified in school. Either way, I ended up doing it as the prompt did not say "don't change the original lists."

To solve Issue #2, I implemented an if-else chain to deal with varies situations with calculating a sum that was greater than or equal to 10.

To solve Issue #3, I ended up using the given struct since LeetCode will be using it when judging my code. It was difficult to get use to using structs and pointers to make up my lists as I am used to using the C++ STL "list" class.

The Results

After solving the three main issues and fixing a few bugs, I have managed to provide a working "addTwoNumbers" method that satisfied LeetCode's judging!

 I was surprised to get 12 ms of runtime as I feel like I used too many loops. However, I still need to develop my sense of what is "fast" and what is "slow" when it comes to benchmarking.

Conclusion

That will conclude today's post. This problem allowed me to practice using linked lists, single and double pointers, and developing algorithms. I hope you enjoyed reading through this post. I am currently working on another LeetCode problem, so expect a new post soon. Until then, thank you for reading!

Link to source code: https://github.com/EricFlorin/Leetcode-Solutions/blob/master/Add%20Two%20Numbers.cpp