My solutions to Project Euler and LeetCode problems.
More information on Project Euler can be found here. My purpose in doing this is to increase my algorithm skills and learn a bit in the process. Each problem will include my initial thoughts, my initial solution (annotated), and the ideal solution (likely taken from somewhere else). I take notes along the way, so things may be copied from other sites.
Solution guides:
Link: Problem X
Link: Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets; open brackets must be closed in the correct order; every close bracket has a corresponding open bracket of the same type.
Conceptually this makes sense: just keep going deeper until you find the paired closing bracket, then come back out. Implementing it was a pain!
class Solution:
def isValid(self, s: str) -> bool:
stack = []
# check every char in string
for i in range(0,len(s)):
# if opening bracket, push to stack
if ((s[i] == "(") or (s[i] == "[") or (s[i] == "{")):
stack.append(s[i])
# if closing bracket, compare to top of stack
# if they pair, pop the open bracket out of stack
elif ((s[i] == ")") and (len(stack) > 0) and (stack[-1] == "(")):
stack.pop()
elif ((s[i] == "]") and (len(stack) > 0) and (stack[-1] == "[")):
stack.pop()
elif ((s[i] == "}") and (len(stack) > 0) and (stack[-1] == "{")):
stack.pop()
else:
return False
if (len(stack) > 0):
return False
else:
return True
A simple odd length check of the string could be implemented at first to immediately return false.
Link: Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".
This one took a bit because of a misunderstanding with the loop, but it's pretty straightforward. First, find shortest string in the list, since that's the longest possible common prefix. Start with the first word's first letter and check if all the other strings have the same first letter. If no, return the current prefix. If yes, add that letter to the final result. Move to the first word's second letter and check all other strings. Continue in this fashion until the prefix is returned.
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
minlen = len(strs[0])
for i in strs:
if (len(i) < minlen):
minlen = len(i)
prefix = ""
for j in range(0,minlen):
letter = strs[0][j]
for k in range(1,len(strs)):
if (strs[k][j] == letter):
continue
else:
return prefix
prefix += letter
return prefix
Link: Container With Most Water
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.
A nested for loop can be used to brute force this. We start with checking all containers that correspond to the first line. Somewhere in there is the largest container. We then iterate to the next line and check all the rectangles. There's no need to check the previous line because containers are associative. This results in O(n2) time number of iterations through, which can get fairly costly.
class Solution:
def maxArea(self, height: List[int]) -> int:
max = 0
for i in range(len(height)):
dist = 1
for j in range(len(height)-1):
area = dist*min(height[0], height[j+1])
if (area > max):
max = area
dist += 1
height.pop(0)
return max
Sure enough, only 50/60 tests pass, with 51 failing for the time limit being exceeded. After reading the start of an explanation, the two pointer technique is mentioned. To implement, we set the left pointer at index 0 and the right pointer at the last index. A while loop runs until the two indices equal each other. Whichever index has the larger value remains the same and the other one is incremented towards the larger index (e.g., if left has the larger value the right one will be decremented by one (closer to the left)).
class Solution:
def maxArea(self, height: List[int]) -> int:
max = 0
left = 0
right = len(height) - 1
while (left < right):
if (height[left] > height[right]):
area = height[right]*(right-left)
right -= 1
else:
area = height[left]*(right-left)
left += 1
if (area > max):
max = area
return max
Link: Problem 10
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
We can loop through every number from three to two million in steps of two (since even numbers are guaranteed to not be prime) and then add two to make up for it missing at the start. (We cannot start at one because that will be considered a prime number.) One problem: this solution takes an incredibly long time to run—multiple seconds!
sum = 0
for i in range(3,2000000,2):
if isprime(i):
sum += i
print(sum+2)
I've already reduced the search space by half through only checking odd numbers. We will need a sieve to make this more efficient. I call upon the Sieve of Eratosthenes. Let's see if I can code it:
[FINISH]Link: Problem 7
What is the 10001st prime number?
Brute force is obvious: run a simple isprime() function over every odd number from three on and find the 10001st hit.
Link: Problem 6
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Brute force, as usual, is straightforward:
sum_squares = 0
square_sum = 0
for i in range(1,101):
sum_squares += i*i
for j in range (1,101):
square_sum += j
diff = square_sum*square_sum - sum_squares
print(diff)
There is a famous story of Gauss solving for the sum of 1-100 in mere seconds by recognizing that that 1+100, 2+99, ..., 50+51 all equal 101, so the simple formual is 50*101 = 5050. This would keep in at O(N) time, but speed it up a bit.
I could not find a better solution.
Link: Problem 5
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
i = 1
while (i>0):
if is_divisible(i,20):
print(i)
break
else:
i += 1
print(i)
print(i)
Link: Problem 4
Find the largest palindrome made from the product of two 3-digit numbers.
Brute force is obvious here. Create the 1002-long list of products, then work backwards from there by converting each to a string and checking the first and last digit, the second and the penultimate, etc. We cannot start counting down (i.e., for i in range(999,100,-1)) because it would lead to a false positive. We also cannot assume it will be a six-digit number.
largest = 0
for i in range(100,999):
for j in range(100,999):
num = str(i*j)
if (len(num) == 5):
if (num[0] == num[-1]) and (num[1] == num[-2]):
if (int(num) > largest):
largest = int(num)
if(len(num) == 6):
if (num[0] == num[-1]) and (num[1] == num[-2]) and (num[2] == num[-3]):
if (int(num) > largest):
largest = int(num)
print(largest)
Link: Problem 3
What is the largest prime factor of the number 600851475143?
The search space of this is up to the square root of the number. We can also start from the largest number and work backwards until we find the first (or last), and thus largest, prime factor.
num = 600851475143
ss = int(math.sqrt(num))
for i in range(ss,1,-1):
if (num % i == 0) and isprime(i):
break
print(i)
The fanciest method uses the Fundamental Theorem of Arithmetic, stating that:
Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers (ignoring the order).
n = 600851475143
i = 2
while (i * i < n):
while (n % i == 0):
n = n / i
i += 1
print(n)
Link: Problem 2
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Initial thoughts: generate the Fibonacci sequence and check if Fn is even. If so, add to sum.
even_sum = 0
fib1 = 0
fib2 = 1
fib3 = 0
while (fib3 < 4000000):
fib3 = fib1 + fib2
if (fib3 % 2 == 0):
even_sum += fib3
fib1 = fib2
fib2 = fib3
print(even_sum)
Link: Problem 1
Find the sum of all the multiples of 3 or 5 below 1000.
multiples = 0
for i in range (3,1000):
if (i % 3 == 0) or (i % 5 == 0):
multiples += i
I could not find a better solution.