import time
from functools import lru_cache

# --- Compromis temps/espace : mémoïsation contre recalcul ---
def puissance_naive(base: float, exposant: int) -> float:
    # O(exposant) -- multiplication répétée
    resultat = 1.0
    for _ in range(exposant):
        resultat *= base
    return resultat

def puissance_rapide(base: float, exposant: int) -> float:
    # O(log exposant) -- exponentiation rapide par carrés successifs (diviser pour régner)
    if exposant == 0:
        return 1.0
    if exposant % 2 == 0:
        moitie = puissance_rapide(base, exposant // 2)
        return moitie * moitie
    return base * puissance_rapide(base, exposant - 1)

assert abs(puissance_rapide(2, 20) - 2**20) < 1e-6

# --- Éviter la complexité cachée : concaténation de chaînes en boucle ---
def construire_chaine_lente(n: int) -> str:
    # O(n^2) : chaque "+=" sur une string recrée un NOUVEL objet immutable de taille croissante
    resultat = ""
    for i in range(n):
        resultat += str(i)
    return resultat

def construire_chaine_rapide(n: int) -> str:
    # O(n) : accumule dans une liste, une SEULE concaténation finale
    morceaux = [str(i) for i in range(n)]
    return "".join(morceaux)

# --- Éviter la complexité cachée : recherche répétée dans une liste vs un set ---
def intersection_lente(a: list, b: list) -> list:
    # O(n * m) : "in" sur une liste est O(m) à chaque itération
    return [x for x in a if x in b]

def intersection_rapide(a: list, b: list) -> list:
    # O(n + m) : "in" sur un set est O(1) en moyenne
    ensemble_b = set(b)
    return [x for x in a if x in ensemble_b]

# --- Complexité amortie : pourquoi list.append() est O(1) amorti malgré des réallocations ---
# CPython double la capacité du tableau interne à chaque réallocation.
# Sur n append(), le coût total des copies est borné par une série géométrique -> O(n) au total,
# donc O(1) EN MOYENNE par appel, même si CERTAINS appels individuels coûtent O(n).

# --- Mesurer réellement plutôt que supposer ---
def comparer_performances(n: int = 20000) -> dict:
    resultats = {}

    debut = time.perf_counter()
    construire_chaine_lente(n)
    resultats["concat_lente"] = time.perf_counter() - debut

    debut = time.perf_counter()
    construire_chaine_rapide(n)
    resultats["concat_rapide"] = time.perf_counter() - debut

    return resultats   # sur n=20000, la version "rapide" est généralement 10-50x plus rapide

# --- Structures adaptées au problème : le bon choix de structure DOMINE l'algorithme ---
# Besoin                         -> Structure adaptée
# Accès par index                -> list / array (O(1))
# Test d'appartenance fréquent   -> set / frozenset (O(1) moyen)
# Paires clé -> valeur           -> dict (O(1) moyen)
# FIFO                           -> collections.deque (O(1) aux extrémités)
# Toujours le min/max            -> heapq (O(log n) insertion/extraction)
# Préfixes de chaînes            -> Trie (O(longueur))
# Ensembles disjoints évolutifs  -> Union-Find (quasi O(1) amorti)
# Comptage de fréquences         -> collections.Counter (O(1) moyen par incrément)

# --- Limiter la mémoire : générateurs au lieu de listes complètes ---
def carres_liste(n: int) -> list[int]:
    return [i * i for i in range(n)]   # matérialise TOUTE la liste en mémoire -- O(n) espace

def carres_generateur(n: int):
    for i in range(n):
        yield i * i   # produit une valeur à la fois -- O(1) espace, utile pour de très grands n

# Sommer un milliard de carrés sans jamais les stocker tous en mémoire simultanément
somme = sum(carres_generateur(1_000_000))

# --- Profiler avant d'optimiser : ne jamais deviner le goulot d'étranglement ---
import cProfile

def fonction_a_profiler():
    return sum(i * i for i in range(100_000))

# cProfile.run("fonction_a_profiler()")   # affiche le temps passé dans chaque fonction appelée