




import functools
from math import sqrt
from time import time


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   *snake_case_     ,   **snake_case_						):

						'''simple docstring'''


						_UpperCAmelCase													=					time()
						_UpperCAmelCase													=					func(*snake_case_     ,   **snake_case_						)
						_UpperCAmelCase													=					time()
						if int(end - start						) > 0:
												print(f"""{func.__name__} runtime: {(end - start):0.4f} s"""						)
						else:
												print(f"""{func.__name__} runtime: {(end - start) * 1000:0.4f} ms"""						)
						return output


def 							__SCREAMING_SNAKE_CASE  (      snake_case_						):

						'''simple docstring'''


						if n < 0:
												raise Exception("n is negative"						)
						if n == 0:
												return [0]
						_UpperCAmelCase													=					[0, 1]
						for _ in range(n - 1						):
												fib.append(fib[-1] + fib[-2]						)
						return fib


def 							__SCREAMING_SNAKE_CASE  (      snake_case_						):

						'''simple docstring'''


						def fib_recursive_term(snake_case_						) -> int:
												if i < 0:
																		raise Exception("n is negative"						)
												if i < 2:
																		return i
												return fib_recursive_term(i - 1						) + fib_recursive_term(i - 2						)

						if n < 0:
												raise Exception("n is negative"						)
						return [fib_recursive_term(snake_case_						) for i in range(n + 1						)]


def 							__SCREAMING_SNAKE_CASE  (      snake_case_						):

						'''simple docstring'''


						@functools.cache
						def fib_recursive_term(snake_case_						) -> int:
												if i < 0:
																		raise Exception("n is negative"						)
												if i < 2:
																		return i
												return fib_recursive_term(i - 1						) + fib_recursive_term(i - 2						)

						if n < 0:
												raise Exception("n is negative"						)
						return [fib_recursive_term(snake_case_						) for i in range(n + 1						)]


def 							__SCREAMING_SNAKE_CASE  (      snake_case_						):

						'''simple docstring'''


						if n < 0:
												raise Exception("n is negative"						)
						# Cache must be outside recursuive function
						# other it will reset every time it calls itself.
						_UpperCAmelCase													=					{0: 0, 1: 1, 2: 1}  # Prefilled cache

						def rec_fn_memoized(snake_case_						) -> int:
												if num in cache:
																		return cache[num]

												_UpperCAmelCase													=					rec_fn_memoized(num - 1						) + rec_fn_memoized(num - 2						)
												_UpperCAmelCase													=					value
												return value

						return [rec_fn_memoized(snake_case_						) for i in range(n + 1						)]


def 							__SCREAMING_SNAKE_CASE  (      snake_case_						):

						'''simple docstring'''


						if n < 0:
												raise Exception("n is negative"						)
						if n >= 1475:
												raise Exception("n is too large"						)
						_UpperCAmelCase													=					sqrt(5						)
						_UpperCAmelCase													=					(1 + sqrt_a) / 2
						return [round(phi**i / sqrt_a						) for i in range(n + 1						)]


if __name__ == "__main__":
				lowercase_     :    List[Any]      =			30
				time_func(fib_iterative, num)
				time_func(fib_recursive, num)  # Around 3s runtime
				time_func(fib_recursive_cached, num)  # Around 0ms runtime
				time_func(fib_memoization, num)
				time_func(fib_binet, num)










from __future__ import annotations


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_						):

						'''simple docstring'''


						_UpperCAmelCase													=					{}
						for index, val in enumerate(snake_case_						):
												_UpperCAmelCase													=					target - val
												if compl in chk_map:
																		return [chk_map[compl], index]
												_UpperCAmelCase													=					index
						return []


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				print(f"""{two_sum([2, 7, 11, 15], 9) = }""")




