# Daily Coding Practice

`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`
`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.`
`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)`
`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`
`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`
`# 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 + [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))`
`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.`
`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}')`
`233334166668Elapsed time: 0.147s233334166668Elapsed time: 0.091s233334166668Elapsed time: 0.085s233333166668Elapsed time: 0.047s233334166668Elapsed time: 1.892s`
`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.`
`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`
`350,704,366Elapsed time 1: 6.87e-05350,704,366Elapsed time 2: 1.41e-05`
`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 ?`
`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`
`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`
`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.`
`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`
`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?`
`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`
`Problem 9: Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.`
`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`
`Result: 250166416500Elapsed time: 0.0005339449999999246sResult: 250166416500.0Elapsed time: 0.0004587810000000747sResult: 250166416500Elapsed time: 0.08250192500000009sResult: 250166416500Elapsed time: 0.0003878170000000125s`
`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?`
`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]`
`104743Elapsed time: 28.187998713104743Elapsed time: 0.025195286000002426`
`Problem 11: There exists exactly one Pythagorean triplet for which a + b + c = 1000.Find the product abc.`
`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`
`31875000Elapsed time: 0.10941719999999999`
`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`
`142913828922Elapsed time: 0.931350436142913828922Elapsed time: 5.024537872`
`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?`
`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[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 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 = [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 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`
`842161320Elapsed time: 33.547493919842161320Elapsed time: 35.008808852`
`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?`
`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] = 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`
`837799Elapsed time: 33.027882943837799Elapsed time: 21.750060497837799Elapsed time: 1.347648270999997`
`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.`
`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 = [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 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`
`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`
`Problem 16: How many connected groups there are given a matrix`
`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`
`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.`
`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 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`
`Elapsed time: 0.00032870199999956995Elapsed time: 0.00019004899999996994`
`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.`
`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.`
`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)`
`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`
`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?`
`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)`
`Problem 21: Find the sum of the digits in the number 100!`
`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)))`
`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.`
`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 ''`
`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)`
`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.`
`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 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.`
`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`
`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?`
`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}')`
`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?`
`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 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(ϕ))`
`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.`
`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)`

--

--

## More from K for What?

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

Love podcasts or audiobooks? Learn on the go with our new app.