# 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 = [ * 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: 137Second 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 elementsto 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:

`# Librariesimport bisectimport timedef 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 + 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)) // 2def 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**6start = 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:

`233334166668Elapsed time: 0.147s233334166668Elapsed time: 0.091s233334166668Elapsed time: 0.085s233333166668Elapsed time: 0.047s233334166668Elapsed 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 numbersEach 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 resultdef 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,366Elapsed time 1: 6.87e-05350,704,366Elapsed time 2: 1.41e-05`

Good? Let’s go to next problem:

`Problem 6: Largest prime factorThe 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 = 600851475143start = time.perf_counter()result = find_largest_prime(number)print(result)end = time.perf_counter()print(f'Elapsed time: {end - start}')6857Elapsed 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 productA 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 resultdef 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 paldef 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 == reversedef 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_productlargest palindrome made from the product of two 6-digit numbers: 999000000999Elapsed time: 0.64slargest palindrome made from the product of two 6-digit numbers: 999000000999Elapsed time: 0.56slargest palindrome made from the product of two 6-digit numbers: 999000000999Elapsed 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 1def solution(n):    """    :param n: int    :return: smallest positive number that is evenly divisible by all of the numbersfrom 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 numbersfrom 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 resultdef dummy_solution(n):    """    :param n: int    :return: smallest positive number that is evenly divisible by all of the numbersfrom 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 iThe smallest positive multiple of first 20 natural numbers is 232792560Elapsed time: 96.987sThe smallest positive multiple of first 20 natural numbers is 232792560.0Elapsed 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_squaresdef 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_squaresdef 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 resultdef 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: 250166416500Elapsed time: 0.0005339449999999246sResult: 250166416500.0Elapsed time: 0.0004587810000000747sResult: 250166416500Elapsed time: 0.08250192500000009sResult: 250166416500Elapsed 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 is13. 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 Truedef 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-1def 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:

`104743Elapsed time: 28.187998713104743Elapsed 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:

`31875000Elapsed 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.`

`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 Truedef 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:

`142913828922Elapsed time: 0.931350436142913828922Elapsed time: 5.024537872`

Thank you for your time. Now’s time for sleeping. Bonne nuit! In next 10 years, I will be at the best place in the world. Now I don’t know where it is but my home

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 countdef 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 triangledef 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 = 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 divisorsdef 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 =  * 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 divisorsdef 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:

`842161320Elapsed time: 33.547493919842161320Elapsed 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 → 1It 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 resultdef 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 resultdef 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 targetdef 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 targetdef 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    dic = 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:

`837799Elapsed time: 33.027882943837799Elapsed time: 21.750060497837799Elapsed 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 resultdef 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 resultdef 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 =  * 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 ansdef 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: How 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 == query_stack:                pattern_stack.popleft()                query_stack.popleft()            elif query_stack.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 resultdef 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 Nonedef 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.00032870199999956995Elapsed 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    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 resdef 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 resdef 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: 0Average elapsed time: 0.68427sNumber of out-of-time cases: 0Average 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 secondparameter 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 Truedef 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 eachof 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 = 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 ddef 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 pairsdef 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 thenumber. 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 thatall 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 abundantnumbers.`

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 dictionarydef 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] > ndef 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 totaldef isabundant(num):    if getdivisors(num) > num:        return True    else:        return False`

The first runs faster than the second twice times

`Elapsed time: 2.5295664120000003Elapsed 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   210What 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 9x = '0123456789'ordi = 10 ** 6start = 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 < 10**(k-1):        list_fibo.append(list_fibo + list_fibo)        list_fibo.popleft()        ind += 1    return inddef 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 + bdef 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 + 1def 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*bdef 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 primedef testEquation(a,b):    n = 0    while True:        test = n**2 + a*n + b        if isPrime(test): n += 1        else: break    return nbest = 0besta = 0bestb = 0for a in range (-1000,1001):    for b in range (-1000,1001):        c = testEquation(a,b)        if c > best:            best, besta, bestb = c, a, bprint(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:

Quant Researcher, Data Scientist, Food Hater (so I eat them a lot).