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
Use division
My algorithm
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: 137
Second 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 elements
to the right of that element in the original input array.
For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1,0]
• There is 1 smaller element to the right of 3
• There is 1 smaller element to the right of 4
• There are 2 smaller elements to the right of 9 • There is 1 smaller element to the right of 6
• There are no smaller elements to the right of 1
# Libraries
import bisect
import time


def solution1(array):
array_length = len(array)
if array_length <= 1:
return []
result = []
for i in range(array_length - 1):
count = 0
for j in range(i+1, array_length):
if array[j] < array[i]:
count += 1
result.append(count)
return result + [0]


def solution2(array):
"""
Utilize bisect module
:param array:list of integers
:return: result: list of integers
"""
result = []
seen = []
for num in reversed(array):
i = bisect.bisect_left(seen, num)
result.append(i)
bisect.insort(seen, num)
return list(reversed(result))
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_5
def set_of_multiple_of_m(m, n):
"""
:param n: integer
:param m: integer, = 3 or = 5
:return: set of multiples of m which are less than n
"""
return set([m*i for i in range(int(n/m)+1)])
def arithmetic_sum(numb, limit):
for last in range(limit, 1, -1):
if last % numb == 0:
return ((limit // numb) * (numb + last)) // 2


def math_power(n):
ans, limit = 0, n
ans += arithmetic_sum(3, limit)
ans += arithmetic_sum(5, limit)
ans -= arithmetic_sum(15, limit)
return ans
number = 10**6
start = time.perf_counter()
print(sum(list_multiple_of_3_or_5(number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum(set_multiple_of_3_or_5(number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum(set_of_multiple_of_m(3, number)) + sum(set_of_multiple_of_m(5, number)) - sum(set_of_multiple_of_m(15,
number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum({*range(3, number, 3)} | {*range(5, number, 5)}))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(math_power(number))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
233334166668
Elapsed time: 0.147s
233334166668
Elapsed time: 0.091s
233334166668
Elapsed time: 0.085s
233333166668
Elapsed time: 0.047s
233334166668
Elapsed time: 1.892s
It’s Sunday, my favorite day in week
Problem 5: Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
def list_fibonacci(n):
"""
:param n: integer, threshold value
:return: list of fibonacci numbers not greater than n
"""
result = [1, 1]
while result[-1] + result[-2] <= n:
result.append(result[-1] + result[-2])
return result


def list_even_fibonacci(n):
"""
Recurrence for Even Fibonacci sequence is:
EFn = 4EFn-1 + EFn-2
with seed values
EF0 = 0 and EF1 = 2.
EFn represents nth term in Even Fibonacci sequence.
:param n: integer, threshold value
:return: list of even fibonacci numbers not greater than n
"""
result = [0, 2]
while 4*result[-1] + result[-2] <= n:
result.append(4*result[-1] + result[-2])
return result
350,704,366
Elapsed time 1: 6.87e-05
350,704,366
Elapsed time 2: 1.41e-05
Problem 6: Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600,851,475,143 ?
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 = 600851475143
start = time.perf_counter()
result = find_largest_prime(number)
print(result)
end = time.perf_counter()
print(f'Elapsed time: {end - start}')

6857
Elapsed time: 0.0013s
Love that everyday would like Friday
Problem 7: Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
def solution(n):
"""
:param n: int, number of digits in number
:return: largest palindrome
"""
result = 0
upper_limit = 10**n-1
lower_limit = 10**(n-1)
for i in range(upper_limit, lower_limit-1, -1):

for j in range(upper_limit, i-1, -1):
x = i*j
if x <= result:
break
elif str(x) == str(x)[::-1]:
result = x
else:
continue

return result


def largest_palindrome_product(digits):
min, max, temp, pal = '1', '', 0, 0
for _ in range(1, digits):
min += '0'
for _ in range(0, digits):
max += '9'
min = int(min)-1
max = int(max)
for num1 in range(max, min, -1):
for num2 in range(num1, min, -1):
temp = num1 * num2
if temp < pal:
break
if str(temp) == "".join(reversed(str(temp))):
pal = temp

return pal


def is_palindrome(num):
# return str(num) == str(num)[::-1]
# shall be more efficient than the str operation above
number, reverse = num, 0
while number != 0:
reverse = reverse * 10 + number % 10
number = number // 10
return num == reverse


def medium_solution(n):
first = 10 ** n - 1
max_product = 0
while first > 10 ** (n - 1):
second = first
while second > 10 ** (n - 1):
if first * second < max_product:
break
if is_palindrome(first * second) and first * second > max_product:
max_product = first * second
second -= 1
first -= 1

return max_product
largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 0.64s
largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 0.56s
largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 1.06s
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 1


def solution(n):
"""
:param n: int
:return: smallest positive number that is evenly divisible by all of the numbers
from 1 to n
"""
result = 1
for i in range(1, n+1):
# print(i)
if result % i == 0:
continue
else:
result = result*i/ucln(result, i)

return int(result)


def check_solution(m, n):
"""
Check whether m is the smallest positive number that is evenly divisible by all of the numbers
from 1 to n
:param m: int
:param n: int
:return: True or False
"""
result = True
for i in range(1, n+1):
if m % i != 0:
result = False
break
return result


def dummy_solution(n):
"""
:param n: int
:return: smallest positive number that is evenly divisible by all of the numbers
from 1 to n
"""
total_product = np.prod([i for i in range(1, n+1)])
for i in range(n, total_product+1):
if check_solution(i, n):
return i
The smallest positive multiple of first 20 natural numbers is 232792560
Elapsed time: 96.987s
The smallest positive multiple of first 20 natural numbers is 232792560.0
Elapsed time: 0.308s
It’s Sunday!

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_squares


def solution2(n):
"""
Quick calculation for sum
:param n: int, quantity of natural numbers
:return: int, the difference
"""
# Sum of the squares
sum_of_squares = sum([i ** 2 for i in range(1, n + 1)])
# Square of sum
square_of_sum = (n*(n+1)/2) ** 2
return square_of_sum - sum_of_squares


def solution3(n):
"""
:param n: int, quantity of natural numbers
:return: int, the difference
"""
result = sum([2*i*j for i in range(1, n) for j in range(i+1, n+1)])
return result


def solution4(n):
"""
:param n: int, quantity of natural numbers
:return: int, the difference
"""
s = 0
sum_of_squares = 0
for i in range(1, n+1):
s += i
sum_of_squares += i**2
return s**2 - sum_of_squares
Result: 250166416500
Elapsed time: 0.0005339449999999246s
Result: 250166416500.0
Elapsed time: 0.0004587810000000747s
Result: 250166416500
Elapsed time: 0.08250192500000009s
Result: 250166416500
Elapsed time: 0.0003878170000000125s
Lily of the Valley — Flower of May
Problem 10: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is
13. What is the 10,001st prime number?
def check_prime(n):
"""
Determine whether n is prime or not
:param n: int
:return: logical value (True/False
"""
if n < 2:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
else:
for i in range(3, n):
if n % i == 0:
return False
return True


def solution1(n):
"""
Find the nth prime
:param n: int, order of the prime
:return: the value of nth prime
"""
count = 0
number = 2
while count < n:
if check_prime(number):
count += 1
number += 1
return number-1


def solution2(n):
"""
We will build a list of primes then find the nth element of the list
p_n < n*(log(n) + log(log(n))
See Ref: https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-prime/
and
https://en.wikipedia.org/wiki/Prime_number_theorem
:param n: int, order of the prime
:return: the value of nth prime
"""
upper_bound = int(n*(math.log(n) + math.log(math.log(n))))
array = [False, False] + [True]*(upper_bound-1)
list_primes = []
for i in range(2, len(array)):
if array[i]:
list_primes.append(i)
for j in range(2, int(len(array)/i)):
array[i*j] = False
return list_primes[n-1]
104743
Elapsed time: 28.187998713
104743
Elapsed 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
31875000
Elapsed time: 0.10941719999999999
Growth Seeker
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 True


def solution2(n):
"""
Run a loop to find all primes less than n, then calculate the sum of them
:param n: int
:return: int
"""
total = 0
for i in range(2, n):
if checkPrime(i):
total += i
return total
142913828922
Elapsed time: 0.931350436
142913828922
Elapsed time: 5.024537872
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
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 count


def solution1(m):
"""
Find the first triangle number that has number of divisors more than m
:param m: int, threshold
:return: int, triangle number that has number of divisors more than m
"""
triangle = 1
count = 2
while count_divisor(triangle) < m:
triangle += count
count += 1
return triangle


def SieveOfEratosthenes(n, prime, primesquare, a):
# Create a boolean array "prime[0..n]"
# and initialize all entries it as
# true. A value in prime[i] will finally
# be false if i is not a prime, else true.
for i in range(2, n + 1):
prime[i] = True

# Create a boolean array "primesquare[0..n*n+1]"
# and initialize all entries it as false.
# A value in squareprime[i] will finally be
# true if i is square of prime, else false.
for i in range((n * n + 1) + 1):
primesquare[i] = False

# 1 is not a prime number
prime[1] = False

p = 2
while p * p <= n:
# If prime[p] is not changed,
# then it is a prime
if prime[p]:
# Update all multiples of p
i = p * 2
while i <= n:
prime[i] = False
i += p
p += 1

j = 0
for p in range(2, n + 1):
if prime[p]:
# Storing primes in an array
a[j] = p

# Update value in primesquare[p*p],
# if p is prime.
primesquare[p * p] = True
j += 1


# Function to count divisors
def countDivisors(n):
# If number is 1, then it will
# have only 1 as a factor. So,
# total factors will be 1.
if n == 1:
return 1

prime = [False] * (n + 2)
primesquare = [False] * (n * n + 2)

# for storing primes upto n
a = [0] * n

# Calling SieveOfEratosthenes to
# store prime factors of n and to
# store square of prime factors of n
SieveOfEratosthenes(n, prime, primesquare, a)

# ans will contain total
# number of distinct divisors
ans = 1

# Loop for counting factors of n
i = 0
while 1:
# a[i] is not less than cube root n
if a[i] * a[i] * a[i] > n:
break

# Calculating power of a[i] in n.
cnt = 1 # cnt is power of
# prime a[i] in n.
while n % a[i] == 0: # if a[i] is a factor of n
n = n / a[i]
cnt = cnt + 1 # incrementing power

# Calculating number of divisors
# If n = a^p * b^q then total
# divisors of n are (p+1)*(q+1)
ans = ans * cnt
i += 1

# if a[i] is greater than
# cube root of n

n = int(n)
# First case
if prime[n]:
ans = ans * 2

# Second case
elif primesquare[n]:
ans = ans * 3

# Third case
elif n != 1:
ans = ans * 4

return ans # Total divisors


def solution2(m):
"""
Find the first triangle number that has number of divisors more than m
:param m: int, threshold
:return: int, triangle number that has number of divisors more than m
"""
triangle = 1
count = 2
while countDivisors(triangle) < m:
triangle += count
count += 1
return triangle
842161320
Elapsed time: 33.547493919
842161320
Elapsed 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 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
def collatz_sequence(n):
"""
Find list of numbers of collatz sequence starting at n
:param n: int, starting number in collatz sequence
:return: list, collatz sequence starting at n
"""
result = list([])
while n != 1:
result.append(int(n))
if n % 2 == 0:
n /= 2
else:
n = 3*n + 1
result.append(1)

return result


def len_collatz_sequence(n):
"""
Find length of collatz sequence starting at n
:param n: int, starting number in collatz sequence
:return: list, collatz sequence starting at n
"""
result = 1
while n != 1:
result += 1
if n % 2 == 0:
n /= 2
else:
n = 3 * n + 1

return result


def solution1(m):
"""
starting number, under m, produces the longest collatz chain
:param m: positive int
:return: positive int, starting number, under m, produces the longest collatz chain
"""
target = 1
max_length_collatz_sequence = 1
for i in range(2, m+1):
length_collatz_sequence = len(collatz_sequence(i))
if length_collatz_sequence > max_length_collatz_sequence:
target = i
max_length_collatz_sequence = length_collatz_sequence

return target


def solution2(m):
"""
starting number, under m, produces the longest collatz chain
:param m: positive int
:return: positive int, starting number, under m, produces the longest collatz chain
"""
target = 1
max_length_collatz_sequence = 1
for i in range(2, m + 1):
length_collatz_sequence = len_collatz_sequence(i)
if length_collatz_sequence > max_length_collatz_sequence:
target = i
max_length_collatz_sequence = length_collatz_sequence

return target


def solution3(m):
"""
Build a list that count number of collatz sequence that starts from a number from 1 to m
:param m: positive int
:return: list
"""
# dictionary with all the values initialized to 0
dic = {n: 0 for n in range(1, m+1)}
# Entering the values of 1 and 2
dic[1] = 1
dic[2] = 2
# for loop find find the size of collatz sequences
for n in range(3, m+1, 1):
# counter to count the size for each iteration
counter = 0
# original number
original_number = n
# while loop to do collatz iterations
while n > 1:
# check if the number is a previous sequence
if n < original_number:
# Size of collatz sequence for the iteration
dic[original_number] = dic[n] + counter
break
# collatz sequence conditions
if n % 2 == 0:
n = n / 2
counter += 1
else:
n = 3 * n + 1
counter += 1
# dic.values() will give the values of the dictionary
# list.index(some_number) will output the index
# of the number. As the index starts from 0
# we are adding one to the index.
maximum = max(dic, key=dic.get)

return maximum
837799
Elapsed time: 33.027882943
837799
Elapsed time: 21.750060497
837799
Elapsed time: 1.347648270999997
Work, Eat, Love
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 result


def solution2(arr):
"""
Optimize the solution1
:param arr: array
:return: list of distance metric of elements in arr
"""
result = []
for i in range(len(arr)):
distance_of_ith = sum([abs(j-i) for j in range(len(arr)) if arr[i] == arr[j]])
result.append(distance_of_ith)

return result


def solution3(arr):
n = len(arr)
# Stores indices of each
# array element
mp = defaultdict(lambda: [])

# Store the indices
for i in range(n):
mp[arr[i]].append(i)

# Stores the sums
ans = [0] * n

# Traverse the array
for i in range(n):

# Find sum for each element
s = 0

# Iterate over the Map
for it in mp[arr[i]]:
# Calculate sum of
# occurrences of arr[i]
s += abs(it - i)

# Store sum for
# current element
ans[i] = s

return ans


def solution4(arr):
"""
Use dictionary to calculate the distance metric of elements in arr
:param arr: array
:return: list of distance metric of elements in arr
"""
dictionary = {}
n = len(arr)
# initiate a dictionary whose keys are distinct values in arr
for i in range(n):
dictionary[arr[i]] = []
# values of each key in dictionary is list of indexes in arr where their values == key
for i in range(n):
dictionary[arr[i]].append(i)
result = []
for i in range(n):
s = 0
for j in dictionary[arr[i]]:
s += abs(j-i)
result.append(s)

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


def split_a_string(s):
"""
Split a string at its uppercase
:param s: str
:return: list of substrings which start at an uppercase
"""
if len(s):
return re.split('(?=[A-Z])', s)
else:
return None


def check_match(s, pattern):
upper_case_s1 = re.findall('[A-Z]', s)
upper_case_s2 = re.findall('[A-Z]', pattern)
if upper_case_s1 != upper_case_s2:
return False
split_s1 = split_a_string(s)
split_s2 = split_a_string(pattern)
for i in range(len(split_s2)):
if split_s2[i] not in split_s1[i]:
return False

return True
Elapsed time: 0.00032870199999956995
Elapsed 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
Springs, Summer, Autumn, Winter, then Springs (again)
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 res


def solution3(lst):
"""
Improved the solution2
With the conditions of input, if the sum of two elements in lst is power of two, it will be
in [1, 2, 4, 8, 16, 32, 64, 128, 256, ..., 2^21]
:param lst: list of positive integers
:return: int, number of pairs of two integers in lst that satisfy the condition
"""
possible_power_of_two = [2 ** i for i in range(22)]
dic = defaultdict(lambda: 0)
for i1 in lst:
dic[i1] += 1
list_of_distinct_element = list(dic.keys())
length_of_distinct_element = len(list_of_distinct_element)
res = 0
for i1 in list_of_distinct_element:
if 2 * i1 in possible_power_of_two:
res += dic[i1]*(dic[i1]-1)/2
for i2 in possible_power_of_two:
i3 = i2 - i1
condition1 = i3 != i1
condition2 = i3 > 0
if condition1 & condition2:
res += dic[i1] * dic[i3]/2

return res


def countPairs(deliciousness):
def sumOfAP(n):
return n * (n - 1) // 2

c = Counter(deliciousness)
powerOfTwos = {2 ** i for i in range(22)}
possibilities = 0
for x in c.keys():
if x * 2 in powerOfTwos:
possibilities += sumOfAP(c[x])
for i in powerOfTwos:
y = i - x
if y != x and y > -1:
possibilities += c[x] * c[y]
c[x] = 0
return possibilities % (10 ** 9 + 7)
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: 0
Average elapsed time: 0.68427s
Number of out-of-time cases: 0
Average elapsed time: 0.59927s
Burning Cold by Cullan Smith on Unsplash
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)))
Photo by Marcel Strauß on Unsplash.com
Problem 22: Have the function MinWindowSubstring(strArr) take the array of strings stored in strArr, which will contain only two strings, the first parameter being the string N and the second
parameter being a string K of some characters, and your goal is to determine the smallest substring of N that contains all the characters in K.
def sublist(lst1, lst2):
"""
Check where list2 is sublist of list1
:param lst1: list
:param lst2: list
:return: boolean
"""
c1 = Counter(lst1)
c2 = Counter(lst2)
for item, count in c2.items():
if count > c1[item]:
return False
return True


def solution1(str1, str2):
"""
convert str2 to a list of characters. search the substring of str1 such that it contains all
characters of str2
:param str1: str
:param str2: str
:return: substring of str1 contains all characters of str2
"""
if len(str1) < len(str2):
print('string1 must not be shorter than string2')
return ''
str2_to_list = list(str2)
len_of_substring = len(str2)
while len_of_substring <= len(str1):

for i in range(len(str1) - len_of_substring +1):
substring = str1[i:i+len_of_substring]
substring_to_list = list(substring)
if sublist(substring_to_list, str2_to_list):
print(substring)
return substring

len_of_substring += 1

print('No substring satisfies the condition')
return ''
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 each
of 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 d

def amicables(k):
d = divisor_sums(k)
pairs = []
for a in range(2,k):
b = d[a]
if a != b and b < k and a == d[b]:
pairs.append((a, b))
return pairs

def solution2(k):
pairs = amicables(k)
return sum(a+b for a,b in pairs if a < b)
author Clique Images on Unsplash
Problem 24: A perfect number is a number for which the sum of its proper divisors is exactly equal to the
number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that
all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant
numbers.
def sum_of_proper_divisors(n):
"""
Compute a list of sums of proper divisors of pos. integers less than n
:param n: pos. integer
:return: list of pos. integers
"""
k = int(n ** (1 / 2))
dictionary = {i: 1 for i in range(2, n)}
for i in range(2, k):
for j in range(2, int(n / i)):
l = i * j
dictionary[l] += i
if j >= k:
dictionary[l] += j

return dictionary


def check_abundant(n, dictionary):
"""
Check whether a positive integer is an abundant number
:param n: pos. integer
:param dictionary: dictionary, sums of all proper divisors of integers
:return: boolean
"""
return dictionary[n] > n


def list_abundant(n, dictionary):
"""
list of abundant numbers less than n
:param n: pos. int
:param dictionary: dictionary
:return: list
"""
return [i for i in range(2, n) if check_abundant(i, dictionary)]


def getdivisors(num):
n = math.ceil(math.sqrt(num))
total = 1
divisor = 2
while divisor < n:
if num % divisor == 0:
total += divisor
total += num // divisor
divisor += 1
return total


def isabundant(num):
if getdivisors(num) > num:
return True
else:
return False
Elapsed time: 2.5295664120000003
Elapsed time: 4.882383252
by Matt Barton on Unsplash
Problem 25: A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. 
If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
def lexicographical_permutation(string, order):
"""
First create a list of permutations by using itertools.permutations.
Second, sorted the list.
Last, find the order-th element.
:param string: str
:param order: the position of the element in sorted list of
permutations
:return: the element order-th in the list
"""
perm = sorted(''.join(chars) for chars in permutations(string))

return perm[order - 1]


# Find the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9
x = '0123456789'
ordi = 10 ** 6
start = time.perf_counter()
print(lexicographical_permutation(x, ordi))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
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 ind


def using_binet_formula(k):
"""
See the Binet formula at https://en.wikipedia.org/wiki/Fibonacci_number#Binet's_formula
"""
if k < 2:
return 1
ϕ = (1 + 5 ** 0.5) / 2

return ceil((k + log10(5) / 2 - 1) / log10(ϕ))
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 + b


def count_consecutive_primes(a, b, lst_of_primes):
n = 0
f = fun(n, a, b)
if f not in lst_of_primes:
return 0
while f in lst_of_primes:
n += 1
f = fun(n, a, b)

return n + 1


def max_number_of_primes(lst_of_primes):
# b must be a prime, 80 <= b <= 1000
# a must be a odd number, |a| < |b|,and |a| <= 1000
max_num = 80
a = -79
b = 1601
list_a = [i for i in range(-1000, 1001) if i % 2 == 1]
print(len(list_a))
list_b = [i for i in range(-1000, 1001) if abs(i) in lst_of_primes]
print(len(list_b))

for i in list_b:
for j in list_a:
value_at_max_num = max_num**2 + j*max_num + i
if (abs(j) < abs(i)) & (value_at_max_num in lst_of_primes):
num_consecutive_primes = count_consecutive_primes(j, i, lst_of_primes)
if num_consecutive_primes > max_num:
max_num = num_consecutive_primes
a, b = j, i

print(a, b, a*b)

return a*b


def isPrime(num):
prime = True
if num < 2: return False
if num == 2: return True
for factor in range(3,int(math.sqrt(num)),2):
if num % factor == 0: prime = False
return prime

def testEquation(a,b):
n = 0
while True:
test = n**2 + a*n + b
if isPrime(test): n += 1
else: break
return n


best = 0
besta = 0
bestb = 0
for a in range (-1000,1001):
for b in range (-1000,1001):
c = testEquation(a,b)
if c > best:
best, besta, bestb = c, a, b

print(besta*bestb)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store