Problème
Un tableau dynamique comme std::vector en C++ stocke ses éléments dans un seul bloc de mémoire. Quand le bloc est plein et qu'un nouvel élément arrive, il alloue un bloc deux fois plus grand, copie les éléments existants, puis libère l'ancien.
Commence avec un tableau vide de capacité initial_capacity et ajoute pushes éléments un par un. Avant chaque ajout, si size == capacity, réalloue : compte une réallocation, ajoute la taille actuelle au nombre d'éléments copiés, et double la capacité.
Implémente dynamic_array_growth(pushes, initial_capacity).
Entrée
pushes: Combien d'éléments sont ajoutés.
initial_capacity: La capacité du tableau vide.
Sortie
Retourne [reallocations, copied_elements, final_capacity].
Contraintes
0 ≤ pushes ≤ 10^7
1 ≤ initial_capacity ≤ 10^6
Exemples
Entrée :
pushes = 5
initial_capacity = 1
Sortie attendue :
expected = [3, 7, 8]Entrée :
long long pushes = 5;
long long initial_capacity = 1;
Sortie attendue :
std::vector<long long> expected = {3, 7, 8};Entrée :
long pushes = 5;
long initial_capacity = 1;
Sortie attendue :
long[] expected = new long[] {3, 7, 8};Explication
La capacité passe de 1 → 2 → 4 → 8 lors de l'ajout des 2e, 3e et 5e éléments, en copiant 1 + 2 + 4 = 7 éléments : [3, 7, 8].
Entrée :
pushes = 4
initial_capacity = 4
Sortie attendue :
expected = [0, 0, 4]Entrée :
long long pushes = 4;
long long initial_capacity = 4;
Sortie attendue :
std::vector<long long> expected = {0, 0, 4};Entrée :
long pushes = 4;
long initial_capacity = 4;
Sortie attendue :
long[] expected = new long[] {0, 0, 4};Explication
Les quatre éléments tiennent dans le premier bloc, donc rien n'est réalloué : [0, 0, 4].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Une réallocation n'a lieu que lorsque le tableau est plein.
Indice 2
À chaque fois, tous les éléments sont copiés et la capacité double.
Indice 3
Vous pouvez sauter d'un doublement au suivant au lieu de simuler chaque push.
Complexité attendue
temps O(log pushes), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.