Skip to content

Commit d1b3f5b

Browse files
vicky1999vicky1999
authored
Merge branch 'master' into master
2 parents 2dbf296 + 8ebe8b5 commit d1b3f5b

32 files changed

+1007
-103
lines changed

‎README.md‎

Lines changed: 23 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,7 @@ If you want to uninstall algorithms, it is as simple as:
7272
- [move_zeros](algorithms/arrays/move_zeros.py)
7373
- [n_sum](algorithms/arrays/n_sum.py)
7474
- [automata](algorithms/automata)
75-
- [DFA](algorithms/automata/DFA.py)
75+
- [DFA](algorithms/automata/dfa.py)
7676
- [backtrack](algorithms/backtrack)
7777
- [general_solution.md](algorithms/backtrack/)
7878
- [add_operators](algorithms/backtrack/add_operators.py)
@@ -166,7 +166,7 @@ If you want to uninstall algorithms, it is as simple as:
166166
- [maximum_flow_dfs](algorithms/graph/maximum_flow_dfs.py)
167167
- [all_pairs_shortest_path](algorithms/graph/all_pairs_shortest_path.py)
168168
- [bellman_ford](algorithms/graph/bellman_ford.py)
169-
- [Count Connected Components](algoritms/graph/count_connected_number_of_component.py)
169+
- [Count Connected Components](algorithms/graph/count_connected_number_of_component.py)
170170
- [heap](algorithms/heap)
171171
- [merge_sorted_k_lists](algorithms/heap/merge_sorted_k_lists.py)
172172
- [skyline](algorithms/heap/skyline.py)
@@ -196,19 +196,23 @@ If you want to uninstall algorithms, it is as simple as:
196196
- [valid_sudoku](algorithms/map/valid_sudoku.py)
197197
- [word_pattern](algorithms/map/word_pattern.py)
198198
- [is_isomorphic](algorithms/map/is_isomorphic.py)
199-
- [is_anagram](algorithms/map/is_anagram.py)
199+
- [is_anagram](algorithms/map/is_anagram.py)
200200
- [maths](algorithms/maths)
201+
- [power](algorithms/maths/power.py)
201202
- [base_conversion](algorithms/maths/base_conversion.py)
202203
- [combination](algorithms/maths/combination.py)
203204
- [cosine_similarity](algorithms/maths/cosine_similarity.py)
204205
- [decimal_to_binary_ip](algorithms/maths/decimal_to_binary_ip.py)
205206
- [euler_totient](algorithms/maths/euler_totient.py)
206207
- [extended_gcd](algorithms/maths/extended_gcd.py)
207-
- [factorial](algorithms/maths/factorial.py)
208+
- [factorial](algorithms/maths/factorial.py)
208209
- [gcd/lcm](algorithms/maths/gcd.py)
209210
- [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
210211
- [is_strobogrammatic](algorithms/maths/is_strobogrammatic.py)
212+
- [magic_number](algorithms/maths/magic_number.py)
213+
- [krishnamurthy_number](algorithms/maths/krishnamurthy_number.py)
211214
- [modular_exponential](algorithms/maths/modular_exponential.py)
215+
- [modular_inverse](algorithms/maths/modular_inverse.py)
212216
- [next_bigger](algorithms/maths/next_bigger.py)
213217
- [next_perfect_square](algorithms/maths/next_perfect_square.py)
214218
- [nth_digit](algorithms/maths/nth_digit.py)
@@ -222,14 +226,14 @@ If you want to uninstall algorithms, it is as simple as:
222226
- [hailstone](algorithms/maths/hailstone.py)
223227
- [recursive_binomial_coefficient](algorithms/maths/recursive_binomial_coefficient.py)
224228
- [find_order](algorithms/maths/find_order_simple.py)
225-
- [find_primitive_root](algorithms/maths/find_primitive_root_simple.py)
226-
- [diffie_hellman_key_exchange](algorithms/maths/diffie_hellman_key_exchange.py)
229+
- [find_primitive_root](algorithms/maths/find_primitive_root_simple.py)
230+
- [diffie_hellman_key_exchange](algorithms/maths/diffie_hellman_key_exchange.py)
227231
- [matrix](algorithms/matrix)
228232
- [sudoku_validator](algorithms/matrix/sudoku_validator.py)
229233
- [bomb_enemy](algorithms/matrix/bomb_enemy.py)
230234
- [copy_transform](algorithms/matrix/copy_transform.py)
231235
- [count_paths](algorithms/matrix/count_paths.py)
232-
- [matrix_rotation.txt](algorithms/matrix/matrix_rotation.txt)
236+
- [matrix_exponentiation](algorithms/matrix/matrix_exponentiation.py)
233237
- [matrix_inversion](algorithms/matrix/matrix_inversion.py)
234238
- [matrix_multiplication](algorithms/matrix/multiply.py)
235239
- [rotate_image](algorithms/matrix/rotate_image.py)
@@ -240,6 +244,7 @@ If you want to uninstall algorithms, it is as simple as:
240244
- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py)
241245
- [cholesky_matrix_decomposition](algorithms/matrix/cholesky_matrix_decomposition.py)
242246
- [sum_sub_squares](algorithms/matrix/sum_sub_squares.py)
247+
- [sort_matrix_diagonally](algorithms/matrix/sort_matrix_diagonally.py)
243248
- [queues](algorithms/queues)
244249
- [max_sliding_window](algorithms/queues/max_sliding_window.py)
245250
- [moving_average](algorithms/queues/moving_average.py)
@@ -258,6 +263,7 @@ If you want to uninstall algorithms, it is as simple as:
258263
- [search_rotate](algorithms/search/search_rotate.py)
259264
- [jump_search](algorithms/search/jump_search.py)
260265
- [next_greatest_letter](algorithms/search/next_greatest_letter.py)
266+
- [interpolation_search](algorithms/search/interpolation_search.py)
261267
- [set](algorithms/set)
262268
- [randomized_set](algorithms/set/randomized_set.py)
263269
- [set_covering](algorithms/set/set_covering.py)
@@ -277,11 +283,13 @@ If you want to uninstall algorithms, it is as simple as:
277283
- [meeting_rooms](algorithms/sort/meeting_rooms.py)
278284
- [merge_sort](algorithms/sort/merge_sort.py)
279285
- [pancake_sort](algorithms/sort/pancake_sort.py)
286+
- [pigeonhole_sort](algorithms/sort/pigeonhole_sort.py)
280287
- [quick_sort](algorithms/sort/quick_sort.py)
281288
- [radix_sort](algorithms/sort/radix_sort.py)
282289
- [selection_sort](algorithms/sort/selection_sort.py)
283290
- [shell_sort](algorithms/sort/shell_sort.py)
284291
- [sort_colors](algorithms/sort/sort_colors.py)
292+
- [stooge_sort](algorithms/sort/stooge_sort.py)
285293
- [top_sort](algorithms/sort/top_sort.py)
286294
- [wiggle_sort](algorithms/sort/wiggle_sort.py)
287295
- [stack](algorithms/stack)
@@ -322,16 +330,18 @@ If you want to uninstall algorithms, it is as simple as:
322330
- [judge_circle](algorithms/strings/judge_circle.py)
323331
- [strong_password](algorithms/strings/strong_password.py)
324332
- [caesar_cipher](algorithms/strings/caesar_cipher.py)
333+
- [check_pangram](algorithms/strings/check_pangram.py)
325334
- [contain_string](algorithms/strings/contain_string.py)
326335
- [count_binary_substring](algorithms/strings/count_binary_substring.py)
327336
- [repeat_string](algorithms/strings/repeat_string.py)
328337
- [min_distance](algorithms/strings/min_distance.py)
329338
- [longest_common_prefix](algorithms/strings/longest_common_prefix.py)
330339
- [rotate](algorithms/strings/rotate.py)
331340
- [first_unique_char](algorithms/strings/first_unique_char.py)
332-
- [repeat_substring](algorithms/strings/repeat_substring.py)
333-
- [atbash_cipher](algorithms/strings/atbash_cipher.py)
334-
- [knuth_morris_pratt](algorithms/strings/knuth_morris_pratt.py)
341+
- [repeat_substring](algorithms/strings/repeat_substring.py)
342+
- [atbash_cipher](algorithms/strings/atbash_cipher.py)
343+
- [longest_palindromic_substring](algorithms/strings/longest_palindromic_substring.py)
344+
- [knuth_morris_pratt](algorithms/strings/knuth_morris_pratt.py)
335345
- [tree](algorithms/tree)
336346
- [bst](algorithms/tree/bst)
337347
- [array_to_bst](algorithms/tree/bst/array_to_bst.py)
@@ -349,6 +359,8 @@ If you want to uninstall algorithms, it is as simple as:
349359
- [count_left_node](algorithms/tree/bst/count_left_node.py)
350360
- [num_empty](algorithms/tree/bst/num_empty.py)
351361
- [height](algorithms/tree/bst/height.py)
362+
- [fenwick_tree](algorithms/tree/fenwick_tree]
363+
- [fenwick_tree](algorithms/tree/fenwick_tree/fenwick_tree.py)
352364
- [red_black_tree](algorithms/tree/red_black_tree)
353365
- [red_black_tree](algorithms/tree/red_black_tree/red_black_tree.py)
354366
- [segment_tree](algorithms/tree/segment_tree)
@@ -366,6 +378,7 @@ If you want to uninstall algorithms, it is as simple as:
366378
- [b_tree](algorithms/tree/b_tree.py)
367379
- [binary_tree_paths](algorithms/tree/binary_tree_paths.py)
368380
- [bin_tree_to_list](algorithms/tree/bin_tree_to_list.py)
381+
- [construct_tree_preorder_postorder](algorithms/tree/construct_tree_postorder_preorder.py)
369382
- [deepest_left](algorithms/tree/deepest_left.py)
370383
- [invert_tree](algorithms/tree/invert_tree.py)
371384
- [is_balanced](algorithms/tree/is_balanced.py)

‎algorithms/arrays/flatten.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ def flatten(input_arr, output_arr=None):
1111
if output_arr is None:
1212
output_arr = []
1313
for ele in input_arr:
14-
if isinstance(ele, Iterable):
14+
if not isinstance(ele, str) and isinstance(ele, Iterable):
1515
flatten(ele, output_arr) #tail-recursion
1616
else:
1717
output_arr.append(ele) #produce the result
@@ -25,7 +25,7 @@ def flatten_iter(iterable):
2525
returns generator which produces one dimensional output.
2626
"""
2727
for element in iterable:
28-
if isinstance(element, Iterable):
28+
if not isinstance(element, str) and isinstance(element, Iterable):
2929
yield from flatten_iter(element)
3030
else:
3131
yield element

‎algorithms/dp/fib.py‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,17 @@
1+
'''
2+
In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, called the Fibonacci sequence,
3+
such that each number is the sum of the two preceding ones, starting from 0 and 1.
4+
That is,
5+
F0=0 , F1=1
6+
and
7+
Fn= F(n-1) + F(n-2)
8+
The Fibonacci numbers are the numbers in the following integer sequence.
9+
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….
10+
11+
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
12+
13+
Here, given a number n, print n-th Fibonacci Number.
14+
'''
115
def fib_recursive(n):
216
"""[summary]
317
Computes the n-th fibonacci number recursive.

‎algorithms/maths/__init__.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,3 +19,7 @@
1919
from .find_primitive_root_simple import *
2020
from .diffie_hellman_key_exchange import *
2121
from .num_digits import *
22+
from .power import *
23+
from .magic_number import *
24+
from .krishnamurthy_number import *
25+

‎algorithms/maths/krishnamurthy_number.py‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
"""
2+
A Krishnamurthy number is a number whose sum total of the factorials of each digit is equal to the number itself.
3+
4+
Here's what I mean by that:
5+
6+
"145" is a Krishnamurthy Number because,
7+
1! + 4! + 5! = 1 + 24 + 120 = 145
8+
9+
"40585" is also a Krishnamurthy Number.
10+
4! + 0! + 5! + 8! + 5! = 40585
11+
12+
"357" or "25965" is NOT a Krishnamurthy Number
13+
3! + 5! + 7! = 6 + 120 + 5040 != 357
14+
15+
The following function will check if a number is a Krishnamurthy Number or not and return a boolean value.
16+
"""
17+
18+
19+
def find_factorial(n):
20+
fact = 1
21+
while n != 0:
22+
fact *= n
23+
n -= 1
24+
return fact
25+
26+
27+
def krishnamurthy_number(n):
28+
if n == 0:
29+
return False
30+
sum_of_digits = 0 # will hold sum of FACTORIAL of digits
31+
temp = n
32+
33+
while temp != 0:
34+
35+
# get the factorial of of the last digit of n and add it to sum_of_digits
36+
sum_of_digits += find_factorial(temp % 10)
37+
38+
# replace value of temp by temp/10
39+
# i.e. will remove the last digit from temp
40+
temp //= 10
41+
42+
# returns True if number is krishnamurthy
43+
return (sum_of_digits == n)

‎algorithms/maths/magic_number.py‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
"""Magic Number
2+
A number is said to be a magic number,
3+
if the sum of its digits are calculated till a single digit recursively
4+
by adding the sum of the digits after every addition.
5+
If the single digit comes out to be 1,then the number is a magic number.
6+
7+
Example:
8+
Number = 50113 => 5+0+1+1+3=10 => 1+0=1 [This is a Magic Number]
9+
Number = 1234 => 1+2+3+4=10 => 1+0=1 [This is a Magic Number]
10+
Number = 199 => 1+9+9=19 => 1+9=10 => 1+0=1 [This is a Magic Number]
11+
Number = 111 => 1+1+1=3 [This is NOT a Magic Number]
12+
13+
The following function checks for Magic numbers and returns a Boolean accordingly.
14+
"""
15+
16+
17+
def magic_number(n):
18+
total_sum = 0
19+
20+
# will end when n becomes 0
21+
# AND
22+
# sum becomes single digit.
23+
while n > 0 or total_sum > 9:
24+
25+
# when n becomes 0 but we have a total_sum,
26+
# we update the value of n with the value of the sum digits
27+
if n == 0:
28+
n = total_sum # only when sum of digits isn't single digit
29+
total_sum = 0
30+
total_sum += n % 10
31+
n //= 10
32+
33+
# Return true if sum becomes 1
34+
return total_sum == 1
35+
36+

‎algorithms/maths/modular_inverse.py‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# extended_gcd(a, b) modified from
2+
# https://github.com/keon/algorithms/blob/master/algorithms/maths/extended_gcd.py
3+
4+
def extended_gcd(a: int, b: int) -> [int, int, int]:
5+
"""Extended GCD algorithm.
6+
Return s, t, g
7+
such that a * s + b * t = GCD(a, b)
8+
and s and t are co-prime.
9+
"""
10+
11+
old_s, s = 1, 0
12+
old_t, t = 0, 1
13+
old_r, r = a, b
14+
15+
while r != 0:
16+
quotient = old_r // r
17+
18+
old_r, r = r, old_r - quotient * r
19+
old_s, s = s, old_s - quotient * s
20+
old_t, t = t, old_t - quotient * t
21+
22+
return old_s, old_t, old_r
23+
24+
25+
def modular_inverse(a: int, m: int) -> int:
26+
"""
27+
Returns x such that a * x = 1 (mod m)
28+
a and m must be coprime
29+
"""
30+
31+
s, t, g = extended_gcd(a, m)
32+
if g != 1:
33+
raise ValueError("a and m must be coprime")
34+
return s % m

‎algorithms/maths/power.py‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
def power(a: int, n: int, r: int = None):
2+
"""
3+
Iterative version of binary exponentiation
4+
5+
Calculate a ^ n
6+
if r is specified, return the result modulo r
7+
8+
Time Complexity : O(log(n))
9+
Space Complexity : O(1)
10+
"""
11+
ans = 1
12+
while n:
13+
if n & 1:
14+
ans = ans * a
15+
a = a * a
16+
if r:
17+
ans %= r
18+
a %= r
19+
n >>= 1
20+
return ans
21+
22+
23+
def power_recur(a: int, n: int, r: int = None):
24+
"""
25+
Recursive version of binary exponentiation
26+
27+
Calculate a ^ n
28+
if r is specified, return the result modulo r
29+
30+
Time Complexity : O(log(n))
31+
Space Complexity : O(log(n))
32+
"""
33+
if n == 0:
34+
ans = 1
35+
elif n == 1:
36+
ans = a
37+
else:
38+
ans = power_recur(a, n // 2, r)
39+
ans = ans * ans
40+
if n % 2:
41+
ans = ans * a
42+
if r:
43+
ans %= r
44+
return ans
45+

‎algorithms/matrix/__init__.py‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +0,0 @@
1-

‎algorithms/matrix/matrix_exponentiation.py‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
def multiply(matA: list, matB: list) -> list:
2+
"""
3+
Multiplies two square matrices matA and matB od size n x n
4+
Time Complexity: O(n^3)
5+
"""
6+
n = len(matA)
7+
matC = [[0 for i in range(n)] for j in range(n)]
8+
9+
for i in range(n):
10+
for j in range(n):
11+
for k in range(n):
12+
matC[i][j] += matA[i][k] * matB[k][j]
13+
14+
return matC
15+
16+
def identity(n: int) -> list:
17+
"""
18+
Returns the Identity matrix of size n x n
19+
Time Complecity: O(n^2)
20+
"""
21+
I = [[0 for i in range(n)] for j in range(n)]
22+
23+
for i in range(n):
24+
I[i][i] = 1
25+
26+
return I
27+
28+
def matrix_exponentiation(mat: list, n: int) -> list:
29+
"""
30+
Calculates mat^n by repeated squaring
31+
Time Complexity: O(d^3 log(n))
32+
d: dimesion of the square matrix mat
33+
n: power the matrix is raised to
34+
"""
35+
if n == 0:
36+
return identity(len(mat))
37+
elif n % 2 == 1:
38+
return multiply(matrix_exponentiation(mat, n - 1), mat)
39+
else:
40+
tmp = matrix_exponentiation(mat, n // 2)
41+
return multiply(tmp, tmp)

0 commit comments

Comments
 (0)