Skip to content

Commit 09fbff3

Browse files
author
Мето Трајковски
committed
Updated nth_fibonacci_number.py
1 parent 99cf73d commit 09fbff3

2 files changed

Lines changed: 83 additions & 51 deletions

File tree

‎Other/nth_fibonacci_number.py‎

Lines changed: 74 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
'''
2-
Nth Fibonacci Number
2+
Find Nth Fibonacci Number
33
44
The Fibonacci numbers are the numbers in the following integer sequence.
55
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
@@ -15,7 +15,7 @@
1515
The simplest recursive solution.
1616
Time Complexity: O(2^N) , actually ~1.6^N, the golden ratio
1717
Space Complexity: O(N) , because of the recursion stack
18-
Recursion with memoizing.
18+
Recursion with memoizing. Much faster, 2^N-N less operations.
1919
Time Complexity: O(N)
2020
Space Complexity: O(N)
2121
Dynamic programming.
@@ -24,7 +24,7 @@
2424
Space optimized dynamic programming. (don't need a whole array, only 2 variables are needed)
2525
Time Complexity: O(N)
2626
Space Complexity: O(1)
27-
Matrix multiplication. (matrix power)
27+
Matrix power.
2828
start matrix: | 1 1 |
2929
| 1 0 |
3030
@@ -41,9 +41,12 @@
4141
| Fn+1 Fn |
4242
Time Complexity: O(N)
4343
Space Complexity: O(1)
44-
Optimized matrix multiplication. (faster power function, using divide and conquer approach)
44+
Time optimized matrix power. (using recursive divide and conquer approach)
4545
Time Complexity: O(LogN)
4646
Space Complexity: O(LogN) , because of the recursion stack
47+
Time and space optimized matrix multiplication. (without recursion, just looping)
48+
Time Complexity: O(LogN)
49+
Space Complexity: O(1)
4750
'''
4851

4952

@@ -54,19 +57,23 @@
5457
def fibonacci_1(n):
5558
if (n == 0) or (n == 1):
5659
return n
60+
5761
return fibonacci_1(n - 1) + fibonacci_1(n - 2)
5862

5963

6064
##############
6165
# Solution 2 #
6266
##############
6367

68+
# hashmap
6469
fib = {0: 0, 1: 1}
6570

6671
def fibonacci_2(n):
6772
if n in fib:
6873
return fib[n]
74+
6975
fib[n] = fibonacci_2(n - 1) + fibonacci_2(n - 2)
76+
7077
return fib[n]
7178

7279

@@ -76,7 +83,6 @@ def fibonacci_2(n):
7683

7784
def fibonacci_3(n):
7885
dp = [0 for i in range(max(2, n + 1))]
79-
dp[0] = 0
8086
dp[1] = 1
8187

8288
for i in range(2, n + 1):
@@ -90,13 +96,33 @@ def fibonacci_3(n):
9096
##############
9197

9298
def fibonacci_4(n):
93-
a, b = 1, 0
99+
dp0, dp1 = 0, 1
100+
101+
for i in range(n):
102+
dp0, dp1 = dp1, dp0 + dp1
103+
104+
return dp0
94105

95-
while n > 0:
96-
a, b = a + b, a
97-
n -= 1
98106

99-
return b
107+
#################################
108+
# Helper for the next solutions #
109+
#################################
110+
111+
def matrix_mult(a, b):
112+
''' a = a * b
113+
Matrices (2x2 matrix) Multiplication method used for the next solutions.
114+
The result of multiplication is saved in 'a' (because of that, the reference
115+
shouldn't be changed, only change the values after all computations are completed
116+
because 'b' could be the same reference/matrix as 'a').
117+
'''
118+
a00 = a[0][0]*b[0][0] + a[0][1]*b[1][0]
119+
a01 = a[0][0]*b[0][1] + a[0][1]*b[1][1]
120+
a10 = a[1][0]*b[0][0] + a[1][1]*b[1][0]
121+
a11 = a[1][0]*b[0][1] + a[1][1]*b[1][1]
122+
a[0][0] = a00
123+
a[0][1] = a01
124+
a[1][0] = a10
125+
a[1][1] = a11
100126

101127

102128
##############
@@ -108,16 +134,7 @@ def fibonacci_5(n):
108134
res = [[1, 1], [1, 0]]
109135

110136
for i in range(n):
111-
res = [
112-
[
113-
res[0][0]*fib[0][0] + res[0][1]*fib[1][0],
114-
res[0][0]*fib[0][1] + res[0][1]*fib[1][1]
115-
],
116-
[
117-
res[1][0]*fib[0][0] + res[1][1]*fib[1][0],
118-
res[1][0]*fib[0][1] + res[1][1]*fib[1][1]
119-
]
120-
]
137+
matrix_mult(res, fib)
121138

122139
return res[1][1] # Fn-1 (or change the range(n-1) and use res[0][1] or res[1][0])
123140

@@ -127,39 +144,42 @@ def fibonacci_5(n):
127144
##############
128145

129146
def fibonacci_6(n):
130-
fib = [[1, 1], [1, 0]]
147+
res = [[1, 1], [1, 0]]
131148

132-
# send the matrix by reference
133-
matrix_pow(fib, n + 1)
149+
matrix_pow(res, n + 1)
134150

135-
return fib[1][1] # return Fn-1
151+
return res[1][1] # return Fn-1
136152

137-
def matrix_pow(fib, n):
153+
def matrix_pow(mat, n):
138154
# divide and conquer power function
139155
if (n == 0) or (n == 1):
140156
return
141157

142158
# split on 2, because matrix^k = matrix^(k/2) * matrix^(k/2)
143-
matrix_pow(fib, n // 2)
159+
matrix_pow(mat, n // 2)
144160

145-
matrix_mult(fib, fib)
161+
matrix_mult(mat, mat)
146162
if n % 2 == 1:
147163
# multiply by the start matrix if odd power
148-
matrix_mult(fib, [[1, 1], [1, 0]])
164+
matrix_mult(mat, [[1, 1], [1, 0]])
149165

150-
def matrix_mult(a, b):
151-
a0 = [
152-
a[0][0]*b[0][0] + a[0][1]*b[1][0],
153-
a[0][0]*b[0][1] + a[0][1]*b[1][1]
154-
]
155-
a1 = [
156-
a[1][0]*b[0][0] + a[1][1]*b[1][0],
157-
a[1][0]*b[0][1] + a[1][1]*b[1][1]
158-
]
159-
# don't lose the reference of 'a'
160-
# and don't multiply directly because 'a' has same reference as 'b'
161-
a[0] = a0
162-
a[1] = a1
166+
167+
##############
168+
# Solution 7 #
169+
##############
170+
171+
def fibonacci_7(n):
172+
fib = [[1, 1], [1, 0]]
173+
res = [[1, 1], [1, 0]]
174+
175+
while n > 0:
176+
if n % 2 == 1:
177+
matrix_mult(res, fib)
178+
179+
n = n // 2
180+
matrix_mult(fib, fib)
181+
182+
return res[1][1]
163183

164184

165185
###########
@@ -173,4 +193,16 @@ def matrix_mult(a, b):
173193
print(fibonacci_3(8))
174194
print(fibonacci_4(8))
175195
print(fibonacci_5(8))
176-
print(fibonacci_6(8))
196+
print(fibonacci_6(8))
197+
print(fibonacci_7(8))
198+
199+
200+
# Test 2
201+
# Correct result => 10946
202+
print(fibonacci_1(21))
203+
print(fibonacci_2(21))
204+
print(fibonacci_3(21))
205+
print(fibonacci_4(21))
206+
print(fibonacci_5(21))
207+
print(fibonacci_6(21))
208+
print(fibonacci_7(21))

‎README.md‎

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,7 @@ Output: XXX
4242
Output explanation: XXX
4343
4444
=========================================
45-
Solution explanation
45+
Solution 1 explanation
4646
Time Complexity: O(X)
4747
Space Complexity: O(X)
4848
Solution 2 explanation
@@ -51,19 +51,19 @@ Solution 2 explanation
5151
Space Complexity: O(X)
5252
'''
5353

54-
############
55-
# Solution #
56-
############
54+
##############
55+
# Solution 1 #
56+
##############
5757

58-
def name_of_problem(params):
58+
def name_of_solution_1(params):
5959
# description of code
6060
pass
6161

6262
##############
6363
# Solution 2 #
6464
##############
6565

66-
def name_of_problem_2(params):
66+
def name_of_solution_2(params):
6767
# description of code
6868
pass
6969

@@ -73,12 +73,12 @@ def name_of_problem_2(params):
7373
###########
7474

7575
# Test 1
76-
# Correct result => 'result'
77-
print(name_of_problem('example'))
76+
# Correct result => 'result1'
77+
print(name_of_solution_1('example1'))
7878

7979
# Test 2
8080
# Correct result => 'result2'
81-
print(name_of_problem_2('example2'))
81+
print(name_of_solution_2('example2'))
8282
```
8383

8484
## Courses

0 commit comments

Comments
 (0)