




import functools
from math import sqrt
from time import time

def 						lowercase_ (						_UpperCAmelCase					, *_UpperCAmelCase					, **_UpperCAmelCase		):




	"""simple docstring"""






	A_					:			Optional[int]						=						time()
	A_					:			Dict						=						func(*SCREAMING_SNAKE_CASE__					, **SCREAMING_SNAKE_CASE__		)
	A_					:			Union[str, Any]						=						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 						lowercase_ (						_UpperCAmelCase		):




	"""simple docstring"""






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

def 						lowercase_ (						_UpperCAmelCase		):




	"""simple docstring"""






	def fib_recursive_term(_UpperCAmelCase		) -> 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(SCREAMING_SNAKE_CASE__		) for i in range(n + 1		)]

def 						lowercase_ (						_UpperCAmelCase		):




	"""simple docstring"""






	@functools.cache
	def fib_recursive_term(_UpperCAmelCase		) -> 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(SCREAMING_SNAKE_CASE__		) for i in range(n + 1		)]

def 						lowercase_ (						_UpperCAmelCase		):




	"""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.
	A_					:			dict[int, int]						=						{0: 0, 1: 1, 2: 1}  # Prefilled cache

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

		A_					:			int						=						rec_fn_memoized(num - 1		) + rec_fn_memoized(num - 2		)
		A_					:			Dict						=						value
		return value

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

def 						lowercase_ (						_UpperCAmelCase		):




	"""simple docstring"""






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


if __name__ == "__main__":
		_lowerCamelCase					:     int				       =    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)











"""simple docstring"""

def 						lowercase_ (						_UpperCAmelCase		):




	"""simple docstring"""






	A_					:			Optional[int]						=						9

	while num > 0:
		if num % 10 != digit:
			return False
		num //= 100
		digit -= 1

	return True

def 						lowercase_ (						):




	"""simple docstring"""






	A_					:			Dict						=						1_3890_2663

	while not is_square_form(num * num		):
		if num % 10 == 3:
			num -= 6  # (3 - 6) % 10 = 7
		else:
			num -= 4  # (7 - 4) % 10 = 3

	return num * 10


if __name__ == "__main__":
		print(f'{solution() = }')





