# 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 1

I 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):

"""

:paramn: integer

:return: list of natural integer less than or equal to n such that it is multiple of 3 or 5return [i for i in range(2, n+1) if ((i % 3 == 0) | (i % 5 == 0))]

"""

def set_multiple_of_3_or_5(n):

"""

:paramn: integer

:return: get union of set of multiples of 3 and set of multiples of 5set_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):

"""

:paramn: integer

:paramm: integer, = 3 or = 5

:return: set of multiples of m which are less than nreturn 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.892s

The 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 result

And 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-05

Good? 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 i

This 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):

"""

:paramn: int, number of digits in number

:return: largest palindromeresult = 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

:parama: int

:paramb: int

:return: the largest divisor of two integers a and bx, 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):

"""

:paramn: int

:return: smallest positive number that is evenly divisible by all of the numbersresult = 1

from 1 to n

"""

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

:paramm: int

:paramn: int

:return: True or Falseresult = True

"""

for i in range(1, n+1):

if m % i != 0:

result = False

break

return result

def dummy_solution(n):

"""

:paramn: int

:return: smallest positive number that is evenly divisible by all of the numberstotal_product = np.prod([i for i in range(1, n+1)])

from 1 to n

"""

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_squares

To 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.0003878170000000125s

Done! 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.025195286000002426

A 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*c

The elapsed time is not good as I expected, but somehow it can be accepted:

`31875000`

Elapsed time: 0.10941719999999999

Now 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 total

And this is the result:

`142913828922`

Elapsed time: 0.931350436

142913828922

Elapsed time: 5.024537872

Thank 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 triangle

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

The 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 maximum

The 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 result

For 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_list

Please try to run the codes and to see how different they are. Now I’m moving to next problem.

`Problem 16: H`*ow many connected groups there are given a matrix*

And 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 count

The 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 True

When I check time running of two solutions, I see that there is no difference between them:

`Elapsed time: 0.00032870199999956995`

Elapsed time: 0.00019004899999996994

Anh 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_gen

The 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 False

The 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: