Daily Coding Practice
Hi everyone,
I have made a decision that I need to improve my coding skill day by day to keep track with the lightning pace of data industry’s evolution. In this blog, I’m happy to share with you all problems from books that I challenge myself everyday. Hope that it would be useful for you too! Let’s go!
Problem 1: Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our array is [1,2,3] then output is [6,3,2] .
The problem is easily solved if we can use division: you calculate the total product of all elements, then divide it to each element i of the array to obtain the output.
What if we can’t use division?
I have an ideal of using dynamic programming. Check the code below:
class Problem1():
def _init_(self):
self.alist = a
def left_product_list(self):
prod_list = []
for number in a:
if len(prod_list):
prod_list.append(prod_list[-1]*number)
else:
prod_list.append(number)
return prod_list
def output(self):
left_prod_list = left_product_list(a)
inversed_a = a[::-1]
right_prod_list = left_product_list(inversed_a)
output = [left_prod_list[i]*right_prod_list[-1-i]/a[i]**2 for i in range(len(a))]
return output
Now I want to test time speed of this algorithm compared with the code using division.
I’m quite happy because my code seems run faster than the benchmark. Beside, when increasing the size of input, the first algorithm can’t work, but my algorithm still does!
Finally I complete first day of coding training. Hope to discuss with you about next problems.
Now it’s time to share with you the second problem.
Problem 2: Given an array of numbers, find the maximum sum of any contiguous subarray of the array. For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, - 5 ,and 86. Given the array [ -5, -1, -8, -9], the maximum sum would be 0, since we would choose not to take any elements.This problem looks hard when I read it because it is not easy even when you solve it in the simplest way: find the maximum among sums of consecutive elements. In general we don’t have any other method to solve it but calculate every sum of subarray, the matter is do it quickly.
My solution is as below:
def Solution(array):
len_of_array = len(array)
A = [[1] * len_of_array for i in range(len_of_array)]
for i in range(len_of_array):
for j in range(len_of_array):
if i == 0:
A[i][j] = array[j]
elif i > j:
A[i][j] = 0
else:
A[i][j] = A[i - 1][j] + array[j - i]
return max(np.max(A), 0)I wrote two samples for testing as below:
array1 = [34, -50, 42, 14, -5, 86]
print(f'First array: {array1}')
print(f'Maximum subarray sum: {Solution(array1)}')
array2 = [ -5, -1, -8, -9]
print(f'Second array: {array2}')
print(f'Maximum subarray sum: {Solution(array2)}')First array: [34, -50, 42, 14, -5, 86]
Maximum subarray sum: 137
Second array: [-5, -1, -8, -9]
Maximum subarray sum: 0
It seems right. I’m really happy if you share your solution with me.
Problem 3: Given an array of integers, return a new array where each element in the new array is the number of smaller elements
to the right of that element in the original input array.
For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1,0]
• There is 1 smaller element to the right of 3
• There is 1 smaller element to the right of 4
• There are 2 smaller elements to the right of 9 • There is 1 smaller element to the right of 6
• There are no smaller elements to the right of 1I tried two different algorithms: The first is go straight to the loop and check step to step, the second is utilizing the bisect module to solve the problem.
The performance of the second is obviously much better than the first’s. Let see how I did as below:
# Libraries
import bisect
import time
def solution1(array):
array_length = len(array)
if array_length <= 1:
return []
result = []
for i in range(array_length - 1):
count = 0
for j in range(i+1, array_length):
if array[j] < array[i]:
count += 1
result.append(count)
return result + [0]
def solution2(array):
"""
Utilize bisect module
:param array:list of integers
:return: result: list of integers
"""
result = []
seen = []
for num in reversed(array):
i = bisect.bisect_left(seen, num)
result.append(i)
bisect.insort(seen, num)
return list(reversed(result))Solution 1 runtime: 2.46s
Solution 2 runtime: 0.009s
This week I were quite busy so I hadn’t done any code till Wednesday. I’m solving a simple but interesting problem in Project Euler.
For anyone who doesn’t know Project Euler, it’s just a website of 746 mathematical problems which are indeed useful for coders to practice their coding skills and algorithmic thinking also. Let’s go straight to the first problem in Project Euler:
Problem 4: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these \
multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.I would like to solve this problem with a general limit n (maybe larger than 1000). The followings are my different solutions for this problem
def list_multiple_of_3_or_5(n):
"""
:param n: integer
:return: list of natural integer less than or equal to n such that it is multiple of 3 or 5
"""
return [i for i in range(2, n+1) if ((i % 3 == 0) | (i % 5 == 0))]
def set_multiple_of_3_or_5(n):
"""
:param n: integer
:return: get union of set of multiples of 3 and set of multiples of 5
"""
set_multiple_of_3 = set([3*i for i in range(int(n/3)+1)])
set_multiple_of_5 = set([5 * i for i in range(int(n/5) + 1)])
return set_multiple_of_3 | set_multiple_of_5def set_of_multiple_of_m(m, n):
"""
:param n: integer
:param m: integer, = 3 or = 5
:return: set of multiples of m which are less than n
"""
return set([m*i for i in range(int(n/m)+1)])def arithmetic_sum(numb, limit):
for last in range(limit, 1, -1):
if last % numb == 0:
return ((limit // numb) * (numb + last)) // 2
def math_power(n):
ans, limit = 0, n
ans += arithmetic_sum(3, limit)
ans += arithmetic_sum(5, limit)
ans -= arithmetic_sum(15, limit)
return ansnumber = 10**6
start = time.perf_counter()
print(sum(list_multiple_of_3_or_5(number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum(set_multiple_of_3_or_5(number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum(set_of_multiple_of_m(3, number)) + sum(set_of_multiple_of_m(5, number)) - sum(set_of_multiple_of_m(15,
number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum({*range(3, number, 3)} | {*range(5, number, 5)}))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(math_power(number))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
And the result for these codes above are as below:
233334166668
Elapsed time: 0.147s
233334166668
Elapsed time: 0.091s
233334166668
Elapsed time: 0.085s
233333166668
Elapsed time: 0.047s
233334166668
Elapsed time: 1.892sThe last solution runs super fast but the code is extremely simple: the trick is utilizing my mathematical skills to quickly calculate the sum of multiples.
Hi everyone, I will continue coding Project Euler problems in this Sunday morning. Let’s see how many problems that I can solve in 3 hours.
Problem 5: Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.Obviously you must find all even Fibonacci numbers which are not greater than four millions. I have two solutions for this problem. The first is simply making a list of all Fibonacci numbers which are not greater than four millions, then calculate sum of all even elements in that list. The second is making a list of all even Fibonacci numbers which are not greater than four millions, then calculate sum of all elements in that list. The later would run faster because I inherit formula to calculate even Fibonacci from previous even numbers in Fibonacci series.
def list_fibonacci(n):
"""
:param n: integer, threshold value
:return: list of fibonacci numbers not greater than n
"""
result = [1, 1]
while result[-1] + result[-2] <= n:
result.append(result[-1] + result[-2])
return result
def list_even_fibonacci(n):
"""
Recurrence for Even Fibonacci sequence is:
EFn = 4EFn-1 + EFn-2
with seed values
EF0 = 0 and EF1 = 2.
EFn represents nth term in Even Fibonacci sequence.
:param n: integer, threshold value
:return: list of even fibonacci numbers not greater than n
"""
result = [0, 2]
while 4*result[-1] + result[-2] <= n:
result.append(4*result[-1] + result[-2])
return resultAnd this is the time elapsed for running each solution with the threshold value is four hundred millions.
350,704,366
Elapsed time 1: 6.87e-05
350,704,366
Elapsed time 2: 1.41e-05Good? Let’s go to next problem:
Problem 6: Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600,851,475,143 ?The solution is following:
def find_largest_prime(n):
"""
:param n: int, threshold value
:return: int, largest prime numbers which are not greater than n
"""
target = n
i = 2
while i <= target:
if target % i == 0:
target /= i
else:
i += 1
return iThis solution is not trivial, because I don’t find out this approach at the first time. Actually I calculate all prime numbers which are less than or equal to n, then pick the largest number that is a divisor of n.
The elapsed time of algorithm is quite impressive:
number = 600851475143
start = time.perf_counter()
result = find_largest_prime(number)
print(result)
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
6857
Elapsed time: 0.0013s
My time is over! I can only solve ONE easy problem in 3 hours :( .
Must work harder next time! See you.
Hi folks, another busy week is passing, finally I can focus to practice coding.
A part of tonight is for solving problems in Project Euler (damn, I love this website so much that I wish I knew it when I was at university!)
Problem 7: Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.I have one solution, these other two below are from other people:
def solution(n):
"""
:param n: int, number of digits in number
:return: largest palindrome
"""
result = 0
upper_limit = 10**n-1
lower_limit = 10**(n-1)
for i in range(upper_limit, lower_limit-1, -1):
for j in range(upper_limit, i-1, -1):
x = i*j
if x <= result:
break
elif str(x) == str(x)[::-1]:
result = x
else:
continue
return result
def largest_palindrome_product(digits):
min, max, temp, pal = '1', '', 0, 0
for _ in range(1, digits):
min += '0'
for _ in range(0, digits):
max += '9'
min = int(min)-1
max = int(max)
for num1 in range(max, min, -1):
for num2 in range(num1, min, -1):
temp = num1 * num2
if temp < pal:
break
if str(temp) == "".join(reversed(str(temp))):
pal = temp
return pal
def is_palindrome(num):
# return str(num) == str(num)[::-1]
# shall be more efficient than the str operation above
number, reverse = num, 0
while number != 0:
reverse = reverse * 10 + number % 10
number = number // 10
return num == reverse
def medium_solution(n):
first = 10 ** n - 1
max_product = 0
while first > 10 ** (n - 1):
second = first
while second > 10 ** (n - 1):
if first * second < max_product:
break
if is_palindrome(first * second) and first * second > max_product:
max_product = first * second
second -= 1
first -= 1
return max_product
largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 0.64s
largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 0.56s
largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 1.06s
Let’s move to next problem:
Problem 8: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?I have 2 solutions for this problem: one is trivial, the other is smarter by utilizing Euclidean algorithm.
def ucln(a, b):
"""
Find the largest divisor of two integers a and b
:param a: int
:param b: int
:return: the largest divisor of two integers a and b
"""
x, y = a, b
while y > 1:
if x == y:
return x
x, y = max(x, y), min(x, y)
x, y = x-y, y
return 1
def solution(n):
"""
:param n: int
:return: smallest positive number that is evenly divisible by all of the numbers
from 1 to n
"""
result = 1
for i in range(1, n+1):
# print(i)
if result % i == 0:
continue
else:
result = result*i/ucln(result, i)
return int(result)
def check_solution(m, n):
"""
Check whether m is the smallest positive number that is evenly divisible by all of the numbers
from 1 to n
:param m: int
:param n: int
:return: True or False
"""
result = True
for i in range(1, n+1):
if m % i != 0:
result = False
break
return result
def dummy_solution(n):
"""
:param n: int
:return: smallest positive number that is evenly divisible by all of the numbers
from 1 to n
"""
total_product = np.prod([i for i in range(1, n+1)])
for i in range(n, total_product+1):
if check_solution(i, n):
return i
The smallest positive multiple of first 20 natural numbers is 232792560
Elapsed time: 96.987s
The smallest positive multiple of first 20 natural numbers is 232792560.0
Elapsed time: 0.308s
You can see again, many coding problem can be solved efficiently if we can utilize our mathematical thinking.
Done! It’s time to take a rest, hope that you’ll have a nice weekend! Bonne nuit!
Hi folks,
in this blog today I just want to solve one Project Euler problem to accomplish weekly mission because I want to spend time for learning Scala and try to solve a Kaggle competition problem. Life is too short to resolve solved problems, right? Here we go:
Problem 9: Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.I tried several ways to solve this problem to understand the efficiency of python when calculating simple maths.
def solution1(n):
"""
:param n: int, quantity of natural numbers
:return: int, the difference
"""
# Sum of the squares
sum_of_squares = sum([i**2 for i in range(1, n+1)])
# Square of sum
square_of_sum = sum([i for i in range(1, n + 1)])**2
return square_of_sum - sum_of_squares
def solution2(n):
"""
Quick calculation for sum
:param n: int, quantity of natural numbers
:return: int, the difference
"""
# Sum of the squares
sum_of_squares = sum([i ** 2 for i in range(1, n + 1)])
# Square of sum
square_of_sum = (n*(n+1)/2) ** 2
return square_of_sum - sum_of_squares
def solution3(n):
"""
:param n: int, quantity of natural numbers
:return: int, the difference
"""
result = sum([2*i*j for i in range(1, n) for j in range(i+1, n+1)])
return result
def solution4(n):
"""
:param n: int, quantity of natural numbers
:return: int, the difference
"""
s = 0
sum_of_squares = 0
for i in range(1, n+1):
s += i
sum_of_squares += i**2
return s**2 - sum_of_squaresTo be honest, it made me a little surprise when the runtime of solution3 is longest. But later I understood the reason why: I ran two overlapped loops so the time complexity is squared.
Result: 250166416500
Elapsed time: 0.0005339449999999246s
Result: 250166416500.0
Elapsed time: 0.0004587810000000747s
Result: 250166416500
Elapsed time: 0.08250192500000009s
Result: 250166416500
Elapsed time: 0.0003878170000000125sDone! It’s time to conquer other missions, see you next week!
Hi, today work is boring me a little bit. Fortunately my soul is healed while practicing coding in the evening. Let’s go through problems today!
Problem 10: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is
13. What is the 10,001st prime number?There is obvious way to solve this problem by defining a function to check whether a number is prime or not, then searching prime number from 2 to so on. Despite of its simplicity, the time complexity is quite high, that’s why I suggest a second solution: we estimate the upper bound of nth prime number, then applying the method of sieve of Eratosthenes to find all prime numbers less than the upper bound.
def check_prime(n):
"""
Determine whether n is prime or not
:param n: int
:return: logical value (True/False
"""
if n < 2:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
else:
for i in range(3, n):
if n % i == 0:
return False
return True
def solution1(n):
"""
Find the nth prime
:param n: int, order of the prime
:return: the value of nth prime
"""
count = 0
number = 2
while count < n:
if check_prime(number):
count += 1
number += 1
return number-1
def solution2(n):
"""
We will build a list of primes then find the nth element of the list
p_n < n*(log(n) + log(log(n))
See Ref: https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-prime/
and
https://en.wikipedia.org/wiki/Prime_number_theorem
:param n: int, order of the prime
:return: the value of nth prime
"""
upper_bound = int(n*(math.log(n) + math.log(math.log(n))))
array = [False, False] + [True]*(upper_bound-1)
list_primes = []
for i in range(2, len(array)):
if array[i]:
list_primes.append(i)
for j in range(2, int(len(array)/i)):
array[i*j] = False
return list_primes[n-1]The running time of the solution 1 is greater than 1000 times the solution 2's:
104743
Elapsed time: 28.187998713
104743
Elapsed time: 0.025195286000002426A little bit surprise, huh?
Tonight I’m still busy with my codes at work, so I spend a little time for project Euler.
Problem 11: There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.I know there is another solution for this problem, but it’s not intuitive for me. My solution is as follows:
def solution1(n):
"""
Find the product abc when a, b, c are Pythagorean triplet such that a + b + c = 1000
:param n: int
:return: int, the product
"""
# assume that a <= b <= c
for a in range(1, int(n/3)):
for c in range(int(n/3)+1, n - 2*a):
b = n - c - a
if b**2 + a**2 == c**2:
return a*b*cThe elapsed time is not good as I expected, but somehow it can be accepted:
31875000
Elapsed time: 0.10941719999999999Now it’s time for coming back to company tasks : I need to write unit tests for my codes, which is the most boring thing in the world as I know. See you in a better day!
Tonight I solved one more problem as below:
Problem 12: Find the sum of all the primes below two million.I had two solutions:
def solution1(n):
"""
Use Sieve of Eratosthenes to find prime numbers less than n, then calculate sum of them
:param n: int, threshold value
:return: int, sum of all primes less than n
"""
array = [False, False] + [True]*(n - 2)
for i in range(2, len(array)):
if array[i]:
for j in range(2, int((len(array) - 1)/i) + 1):
array[i*j] = False
list_primes = [i for i in range(len(array)) if array[i]]
return sum(list_primes)
def checkPrime(n):
"""
Check whether n is prime or not
:param n: int
:return: True or False
"""
if n == 1:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
else:
for i in range(3, int(n**(1/2)) + 1, 2):
if n % i == 0:
return False
return True
def solution2(n):
"""
Run a loop to find all primes less than n, then calculate the sum of them
:param n: int
:return: int
"""
total = 0
for i in range(2, n):
if checkPrime(i):
total += i
return totalAnd this is the result:
142913828922
Elapsed time: 0.931350436
142913828922
Elapsed time: 5.024537872Thank you for your time. Now’s time for sleeping. Bonne nuit!
Hi folks,
It’s Saturday morning, let’s solve the problem below for breakfast:
Problem 13: The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28What is the value of the first triangle number to have over five hundred divisors?
I’ll give you two solutions: the first is mine — simple and clear, the second is from other. I don’t think there is too much different of performance between two solution. When I try with a large number, 1000, my solution is even faster.
def count_divisor(n):
"""
Count number of divisors of n
:param n: int
:return: number of divisors of n
"""
if n <= 0:
print('Number must be positive')
return 0
else:
count = 0
for i in range(1, int(n**(1/2)) + 1):
if n % i == 0:
count += 1
if n/i > i:
count += 1
return count
def solution1(m):
"""
Find the first triangle number that has number of divisors more than m
:param m: int, threshold
:return: int, triangle number that has number of divisors more than m
"""
triangle = 1
count = 2
while count_divisor(triangle) < m:
triangle += count
count += 1
return triangle
def SieveOfEratosthenes(n, prime, primesquare, a):
# Create a boolean array "prime[0..n]"
# and initialize all entries it as
# true. A value in prime[i] will finally
# be false if i is not a prime, else true.
for i in range(2, n + 1):
prime[i] = True
# Create a boolean array "primesquare[0..n*n+1]"
# and initialize all entries it as false.
# A value in squareprime[i] will finally be
# true if i is square of prime, else false.
for i in range((n * n + 1) + 1):
primesquare[i] = False
# 1 is not a prime number
prime[1] = False
p = 2
while p * p <= n:
# If prime[p] is not changed,
# then it is a prime
if prime[p]:
# Update all multiples of p
i = p * 2
while i <= n:
prime[i] = False
i += p
p += 1
j = 0
for p in range(2, n + 1):
if prime[p]:
# Storing primes in an array
a[j] = p
# Update value in primesquare[p*p],
# if p is prime.
primesquare[p * p] = True
j += 1
# Function to count divisors
def countDivisors(n):
# If number is 1, then it will
# have only 1 as a factor. So,
# total factors will be 1.
if n == 1:
return 1
prime = [False] * (n + 2)
primesquare = [False] * (n * n + 2)
# for storing primes upto n
a = [0] * n
# Calling SieveOfEratosthenes to
# store prime factors of n and to
# store square of prime factors of n
SieveOfEratosthenes(n, prime, primesquare, a)
# ans will contain total
# number of distinct divisors
ans = 1
# Loop for counting factors of n
i = 0
while 1:
# a[i] is not less than cube root n
if a[i] * a[i] * a[i] > n:
break
# Calculating power of a[i] in n.
cnt = 1 # cnt is power of
# prime a[i] in n.
while n % a[i] == 0: # if a[i] is a factor of n
n = n / a[i]
cnt = cnt + 1 # incrementing power
# Calculating number of divisors
# If n = a^p * b^q then total
# divisors of n are (p+1)*(q+1)
ans = ans * cnt
i += 1
# if a[i] is greater than
# cube root of n
n = int(n)
# First case
if prime[n]:
ans = ans * 2
# Second case
elif primesquare[n]:
ans = ans * 3
# Third case
elif n != 1:
ans = ans * 4
return ans # Total divisors
def solution2(m):
"""
Find the first triangle number that has number of divisors more than m
:param m: int, threshold
:return: int, triangle number that has number of divisors more than m
"""
triangle = 1
count = 2
while countDivisors(triangle) < m:
triangle += count
count += 1
return triangleThe elapsed time for finding the first triangle number, which has more than 1000 number of divisors, of each solution is below:
842161320
Elapsed time: 33.547493919
842161320
Elapsed time: 35.008808852The lesson here is when we solve a problem, we should try to think simple first.
Now it’s time to begin a new problem as below:
Problem 14: The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.Which starting number, under one million, produces the longest chain?
I have three solutions, the third is the fastest by applying dynamic programming.
def collatz_sequence(n):
"""
Find list of numbers of collatz sequence starting at n
:param n: int, starting number in collatz sequence
:return: list, collatz sequence starting at n
"""
result = list([])
while n != 1:
result.append(int(n))
if n % 2 == 0:
n /= 2
else:
n = 3*n + 1
result.append(1)
return result
def len_collatz_sequence(n):
"""
Find length of collatz sequence starting at n
:param n: int, starting number in collatz sequence
:return: list, collatz sequence starting at n
"""
result = 1
while n != 1:
result += 1
if n % 2 == 0:
n /= 2
else:
n = 3 * n + 1
return result
def solution1(m):
"""
starting number, under m, produces the longest collatz chain
:param m: positive int
:return: positive int, starting number, under m, produces the longest collatz chain
"""
target = 1
max_length_collatz_sequence = 1
for i in range(2, m+1):
length_collatz_sequence = len(collatz_sequence(i))
if length_collatz_sequence > max_length_collatz_sequence:
target = i
max_length_collatz_sequence = length_collatz_sequence
return target
def solution2(m):
"""
starting number, under m, produces the longest collatz chain
:param m: positive int
:return: positive int, starting number, under m, produces the longest collatz chain
"""
target = 1
max_length_collatz_sequence = 1
for i in range(2, m + 1):
length_collatz_sequence = len_collatz_sequence(i)
if length_collatz_sequence > max_length_collatz_sequence:
target = i
max_length_collatz_sequence = length_collatz_sequence
return target
def solution3(m):
"""
Build a list that count number of collatz sequence that starts from a number from 1 to m
:param m: positive int
:return: list
"""
# dictionary with all the values initialized to 0
dic = {n: 0 for n in range(1, m+1)}
# Entering the values of 1 and 2
dic[1] = 1
dic[2] = 2
# for loop find find the size of collatz sequences
for n in range(3, m+1, 1):
# counter to count the size for each iteration
counter = 0
# original number
original_number = n
# while loop to do collatz iterations
while n > 1:
# check if the number is a previous sequence
if n < original_number:
# Size of collatz sequence for the iteration
dic[original_number] = dic[n] + counter
break
# collatz sequence conditions
if n % 2 == 0:
n = n / 2
counter += 1
else:
n = 3 * n + 1
counter += 1
# dic.values() will give the values of the dictionary
# list.index(some_number) will output the index
# of the number. As the index starts from 0
# we are adding one to the index.
maximum = max(dic, key=dic.get)
return maximumThe performance of each solution is as below:
837799
Elapsed time: 33.027882943
837799
Elapsed time: 21.750060497
837799
Elapsed time: 1.347648270999997
Today I have been training my self to prepare for the two coming interviews in tomorrow, so I have solved more coding problems than usual. Let’s review what I have done up to now.
Problem 15: For each element in a given array, calculate the absolute value of index differences between it and all other elements of the same value. Return the resulting values in an array.For example, if the array elements at indices 2 and 3 are equal, the distance metric for element 2 is |2-3| = 1. For element 3 it is|3-2|=1.
I’ll give you 4 solutions for this problem. All of them are right, but the first two solutions run extremely slow compare to the the last two solutions.
def solution1(arr):
"""
Just use lops to calculate distance metric of each element in array
:param arr: array
:return: list of distance metric of elements in arr
"""
result = []
for i in range(len(arr)):
index_same_values = [j for j in range(len(arr)) if arr[i] == arr[j]]
distance_of_ith = sum([abs(j-i) for j in index_same_values])
result.append(distance_of_ith)
return result
def solution2(arr):
"""
Optimize the solution1
:param arr: array
:return: list of distance metric of elements in arr
"""
result = []
for i in range(len(arr)):
distance_of_ith = sum([abs(j-i) for j in range(len(arr)) if arr[i] == arr[j]])
result.append(distance_of_ith)
return result
def solution3(arr):
n = len(arr)
# Stores indices of each
# array element
mp = defaultdict(lambda: [])
# Store the indices
for i in range(n):
mp[arr[i]].append(i)
# Stores the sums
ans = [0] * n
# Traverse the array
for i in range(n):
# Find sum for each element
s = 0
# Iterate over the Map
for it in mp[arr[i]]:
# Calculate sum of
# occurrences of arr[i]
s += abs(it - i)
# Store sum for
# current element
ans[i] = s
return ans
def solution4(arr):
"""
Use dictionary to calculate the distance metric of elements in arr
:param arr: array
:return: list of distance metric of elements in arr
"""
dictionary = {}
n = len(arr)
# initiate a dictionary whose keys are distinct values in arr
for i in range(n):
dictionary[arr[i]] = []
# values of each key in dictionary is list of indexes in arr where their values == key
for i in range(n):
dictionary[arr[i]].append(i)
result = []
for i in range(n):
s = 0
for j in dictionary[arr[i]]:
s += abs(j-i)
result.append(s)
return resultFor testing performances of these solutions, I built a test function like below:
def test():
"""
Create an array randomly has n (where 1<=n<=10^5) integer elements (value in [1, 10^9])
:return: array
"""
n = random.randint(1, 10**5)
print(f'Length of the array: {n}')
num_list = numpy.random.randint(1, 10**9, size=n)
return num_listPlease try to run the codes and to see how different they are. Now I’m moving to next problem.
Problem 16: How many connected groups there are given a matrixAnd my solution is as below:
def count_connected_groups(adj):
adj_standardized = [list(map(int, i)) for i in adj]
n = len(adj_standardized)
nodes_to_check = [i for i in range(n)] # [0, 1, ..., n-1]
count = 0
while n:
count += 1
n -= 1
node = nodes_to_check[n]
adjacent = adj_standardized[node]
i = 0
while i < n:
other_node = nodes_to_check[i]
if adjacent[other_node]:
n -= 1
nodes_to_check[i] = nodes_to_check[n]
else:
i += 1
return countThe solution is quite good in term of time complexity.
Now, I have another problem:
Problem 17: A query word matches a given pattern if we can insert lowercase letters to the pattern word so that it equals the query. (We may insert each character at any position, and may insert 0 characters.)Given a list of queries, and a pattern, return an answer list of booleans, where answer[i] is true if and only if queries[i] matches the pattern.
I have 2 solutions for this problem:
def camel_match(queries: list, pattern: str) -> list:
result = []
for query in queries:
pattern_stack = deque(pattern)
query_stack = deque(query)
while pattern_stack and query_stack:
if pattern_stack[0] == query_stack[0]:
pattern_stack.popleft()
query_stack.popleft()
elif query_stack[0].islower():
query_stack.popleft()
else:
result.append(False)
break
else:
if pattern_stack or any((i.isupper() for i in query_stack)):
result.append(False)
else:
result.append(True)
return result
def split_a_string(s):
"""
Split a string at its uppercase
:param s: str
:return: list of substrings which start at an uppercase
"""
if len(s):
return re.split('(?=[A-Z])', s)
else:
return None
def check_match(s, pattern):
upper_case_s1 = re.findall('[A-Z]', s)
upper_case_s2 = re.findall('[A-Z]', pattern)
if upper_case_s1 != upper_case_s2:
return False
split_s1 = split_a_string(s)
split_s2 = split_a_string(pattern)
for i in range(len(split_s2)):
if split_s2[i] not in split_s1[i]:
return False
return TrueWhen I check time running of two solutions, I see that there is no difference between them:
Elapsed time: 0.00032870199999956995
Elapsed time: 0.00019004899999996994Anh the final problem that i want to share with you is below:
Problem 18: Given an array, reduce the array to a single element with minimum cost. For reducing, remove two elements from the array, add those two numbers and keep the sum back in the array. The cost of each operation is the sum of the elements removed in that step.My solution is based on heap techniques:
def reduce_sum(lst):
"""
Find the minimal cost when reduce an array
:param lst: array of integers
:return: int, minimal cost
"""
heapq.heapify(lst)
s = 0
while len(lst) > 1:
first = heapq.heappop(lst)
second = heapq.heappop(lst)
s += first + second
heapq.heappush(lst, first + second)
# Remain element in array
# lst[0]
return s
Problem 19: A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two. You can pick any two different foods to make a good meal.
Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i item of food, return the number of different good meals you can make from this list modulo 10^9 + 7.
Note that items with different indices are considered different even if they have the same deliciousness value.I have tried four solutions for this problem. The first one is trivial and slowest, the consecutive solutions are improved better and better.
def solution1(lst):
"""
just calculate sum of two elements in lst and check whether it is a power of two
:param lst: list of positive integers
:return: int, number of pairs of two integers in lst that satisfy the condition
"""
length_lst = len(lst)
if length_lst <= 1:
return 0
res = 0
for i1 in range(length_lst - 1):
for i2 in range(i1 + 1, length_lst):
if lst[i1] + lst[i2] > 0:
if math.log2(lst[i1] + lst[i2]) == int(math.log2(lst[i1] + lst[i2])):
res += 1
else:
continue
return res % (10 ** 9 + 7)
def solution2(lst):
"""
With the conditions of input, if the sum of two elements in lst is power of two, it will be
in [1, 2, 4, 8, 16, 32, 64, 128, 256, ..., 2^21]
:param lst: list of positive integers
:return: int, number of pairs of two integers in lst that satisfy the condition
"""
possible_power_of_two = [2 ** i for i in range(22)]
dic = defaultdict(lambda: 0)
for i1 in lst:
dic[i1] += 1
list_of_distinct_element = list(dic.keys())
length_of_distinct_element = len(list_of_distinct_element)
res = 0
for i1 in range(length_of_distinct_element):
for i2 in range(i1, length_of_distinct_element):
if i1 != i2:
if (list_of_distinct_element[i1] + list_of_distinct_element[i2]) in \
possible_power_of_two:
res += dic[list_of_distinct_element[i1]] * dic[list_of_distinct_element[i2]]
else:
if 2*list_of_distinct_element[i1] in possible_power_of_two:
res += dic[list_of_distinct_element[i1]]*(dic[list_of_distinct_element[i1]]-1)/2
return res
def solution3(lst):
"""
Improved the solution2
With the conditions of input, if the sum of two elements in lst is power of two, it will be
in [1, 2, 4, 8, 16, 32, 64, 128, 256, ..., 2^21]
:param lst: list of positive integers
:return: int, number of pairs of two integers in lst that satisfy the condition
"""
possible_power_of_two = [2 ** i for i in range(22)]
dic = defaultdict(lambda: 0)
for i1 in lst:
dic[i1] += 1
list_of_distinct_element = list(dic.keys())
length_of_distinct_element = len(list_of_distinct_element)
res = 0
for i1 in list_of_distinct_element:
if 2 * i1 in possible_power_of_two:
res += dic[i1]*(dic[i1]-1)/2
for i2 in possible_power_of_two:
i3 = i2 - i1
condition1 = i3 != i1
condition2 = i3 > 0
if condition1 & condition2:
res += dic[i1] * dic[i3]/2
return res
def countPairs(deliciousness):
def sumOfAP(n):
return n * (n - 1) // 2
c = Counter(deliciousness)
powerOfTwos = {2 ** i for i in range(22)}
possibilities = 0
for x in c.keys():
if x * 2 in powerOfTwos:
possibilities += sumOfAP(c[x])
for i in powerOfTwos:
y = i - x
if y != x and y > -1:
possibilities += c[x] * c[y]
c[x] = 0
return possibilities % (10 ** 9 + 7)I built a test for these functions as below:
def test():
"""
1 <= deliciousness.length <= 10^5
0 <= deliciousness[i] <= 2^20
:return: list of positive integers
"""
length = random.randint(1, 10 ** 5)
deliciousness_gen = numpy.random.randint(0, 2**20, size=length)
return deliciousness_genThe last two solutions passed my tests in term of speed:
Number of out-of-time cases: 0
Average elapsed time: 0.68427s
Number of out-of-time cases: 0
Average elapsed time: 0.59927s
Problem 20: What is the sum of the digits of the number 2^1000?This is an interesting problem when you extend the exponential number is very large number. Unfortunately I haven’t found the solution for this case yet. The below is solving simple case:
def digit_sum(n):
"""
Calculate sum of digits of a number n
"""
strr = str(n)
list_of_number = list(map(int, strr.strip()))
return sum(list_of_number)The result when n = 2^1000 is 1366.
Problem 21: Find the sum of the digits in the number 100!The simplest solution is below:
def product(n):
"""
Calculate the product of n positive integers counting from 1
:param n: positive int
:return: positive int
"""
if n == 1:
return 1
return n*product(n-1)
def sum_of_digits(n):
"""
Calculate the sum of digits of n
:param n: positive int
:return: positive int
"""
string = str(n)
return sum(list(map(int, string)))for n = 100, the result is 648.
When something that I don’t expect happens, what is the best thing I can do is to focus to my growth path :)
Problem 22: Have the function MinWindowSubstring(strArr) take the array of strings stored in strArr, which will contain only two strings, the first parameter being the string N and the second
parameter being a string K of some characters, and your goal is to determine the smallest substring of N that contains all the characters in K.I think I have a formal solution for this problem:
def sublist(lst1, lst2):
"""
Check where list2 is sublist of list1
:param lst1: list
:param lst2: list
:return: boolean
"""
c1 = Counter(lst1)
c2 = Counter(lst2)
for item, count in c2.items():
if count > c1[item]:
return False
return True
def solution1(str1, str2):
"""
convert str2 to a list of characters. search the substring of str1 such that it contains all
characters of str2
:param str1: str
:param str2: str
:return: substring of str1 contains all characters of str2
"""
if len(str1) < len(str2):
print('string1 must not be shorter than string2')
return ''
str2_to_list = list(str2)
len_of_substring = len(str2)
while len_of_substring <= len(str1):
for i in range(len(str1) - len_of_substring +1):
substring = str1[i:i+len_of_substring]
substring_to_list = list(substring)
if sublist(substring_to_list, str2_to_list):
print(substring)
return substring
len_of_substring += 1
print('No substring satisfies the condition')
return ''When I try to run this code on Coderbyte, its performance is acceptable, but I could improve it more if I optimize the code like below:
def MinWindowSubstring(N, K):
frequencyK = Counter(K)
options = []
for i in range(len(N)):
curr = Counter()
for j in range(i, len(N)):
curr[N[j]] += 1
if frequencyK - curr == EMPTY_COUNTER:
options.append(N[i:j + 1])
break
return min(options, key=len)Let’s try more in the next problem on Coderbyte!
Problem 23: Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each
of a and b are called amicable numbers.I want to show you the solution that uses dynamic programming technique.
def divisor_sums(k):
s = math.ceil(math.sqrt(k))
d = {n:1 for n in range(2,k)}
d[1] = 0
for i in range(2,s):
for j in range(2,k//i):
n = i*j
d[n] += i
if s <= j:
d[n] += j
return d
def amicables(k):
d = divisor_sums(k)
pairs = []
for a in range(2,k):
b = d[a]
if a != b and b < k and a == d[b]:
pairs.append((a, b))
return pairs
def solution2(k):
pairs = amicables(k)
return sum(a+b for a,b in pairs if a < b)
Problem 24: A perfect number is a number for which the sum of its proper divisors is exactly equal to the
number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that
all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant
numbers.I have two solutions. Actually the first is the improved version of the second
def sum_of_proper_divisors(n):
"""
Compute a list of sums of proper divisors of pos. integers less than n
:param n: pos. integer
:return: list of pos. integers
"""
k = int(n ** (1 / 2))
dictionary = {i: 1 for i in range(2, n)}
for i in range(2, k):
for j in range(2, int(n / i)):
l = i * j
dictionary[l] += i
if j >= k:
dictionary[l] += j
return dictionary
def check_abundant(n, dictionary):
"""
Check whether a positive integer is an abundant number
:param n: pos. integer
:param dictionary: dictionary, sums of all proper divisors of integers
:return: boolean
"""
return dictionary[n] > n
def list_abundant(n, dictionary):
"""
list of abundant numbers less than n
:param n: pos. int
:param dictionary: dictionary
:return: list
"""
return [i for i in range(2, n) if check_abundant(i, dictionary)]
def getdivisors(num):
n = math.ceil(math.sqrt(num))
total = 1
divisor = 2
while divisor < n:
if num % divisor == 0:
total += divisor
total += num // divisor
divisor += 1
return total
def isabundant(num):
if getdivisors(num) > num:
return True
else:
return FalseThe first runs faster than the second twice times
Elapsed time: 2.5295664120000003
Elapsed time: 4.882383252
Problem 25: A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4.
If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?By using default module itertools I solve this problem quite smoothly as below:
def lexicographical_permutation(string, order):
"""
First create a list of permutations by using itertools.permutations.
Second, sorted the list.
Last, find the order-th element.
:param string: str
:param order: the position of the element in sorted list of
permutations
:return: the element order-th in the list
"""
perm = sorted(''.join(chars) for chars in permutations(string))
return perm[order - 1]
# Find the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9
x = '0123456789'
ordi = 10 ** 6
start = time.perf_counter()
print(lexicographical_permutation(x, ordi))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')The code runs in 1 second, so I think it’s acceptable.
Problem 26: The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
I tried 2 solutions for this problem. The first I will calculate Fibonacci numbers until I find the first element which has 1000 digits. The second is using Binet formula to estimate the index without calculating any numbers. The second solution runs 100x faster than the first.
def find_the_first_n_digit_fibo(k):
list_fibo = deque([1, 1])
ind = 2
while list_fibo[1] < 10**(k-1):
list_fibo.append(list_fibo[0] + list_fibo[1])
list_fibo.popleft()
ind += 1
return ind
def using_binet_formula(k):
"""
See the Binet formula at https://en.wikipedia.org/wiki/Fibonacci_number#Binet's_formula
"""
if k < 2:
return 1
ϕ = (1 + 5 ** 0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(ϕ))The last coding problem for today is as below:
Problem 27: Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n , starting with n = 0.I have 2 solutions for this problem. I’m quite surprised because the solution which is simple and straightforward runs faster than the other.
def list_of_primes_less_than_n(n):
"""
Calculate a list of primes which are less than or equal to n
:param n: pos. int
:return: list
"""
lst = [False, False] + [True]*(n-1)
for i in range(2, n+1):
if lst[i]:
for j in range(2, int(n/i) + 1):
lst[i*j] = False
else:
continue
return [x for x in range(len(lst)) if lst[x]]
def fun(n, a, b):
return n**2 + a*n + b
def count_consecutive_primes(a, b, lst_of_primes):
n = 0
f = fun(n, a, b)
if f not in lst_of_primes:
return 0
while f in lst_of_primes:
n += 1
f = fun(n, a, b)
return n + 1
def max_number_of_primes(lst_of_primes):
# b must be a prime, 80 <= b <= 1000
# a must be a odd number, |a| < |b|,and |a| <= 1000
max_num = 80
a = -79
b = 1601
list_a = [i for i in range(-1000, 1001) if i % 2 == 1]
print(len(list_a))
list_b = [i for i in range(-1000, 1001) if abs(i) in lst_of_primes]
print(len(list_b))
for i in list_b:
for j in list_a:
value_at_max_num = max_num**2 + j*max_num + i
if (abs(j) < abs(i)) & (value_at_max_num in lst_of_primes):
num_consecutive_primes = count_consecutive_primes(j, i, lst_of_primes)
if num_consecutive_primes > max_num:
max_num = num_consecutive_primes
a, b = j, i
print(a, b, a*b)
return a*b
def isPrime(num):
prime = True
if num < 2: return False
if num == 2: return True
for factor in range(3,int(math.sqrt(num)),2):
if num % factor == 0: prime = False
return prime
def testEquation(a,b):
n = 0
while True:
test = n**2 + a*n + b
if isPrime(test): n += 1
else: break
return n
best = 0
besta = 0
bestb = 0
for a in range (-1000,1001):
for b in range (-1000,1001):
c = testEquation(a,b)
if c > best:
best, besta, bestb = c, a, b
print(besta*bestb)I think I will check the codes again next time. Now it’s time to turn to another task. Enjoy your weekend!
The problems that I discussed are from books below:
Or other online sources as below:
