Problem
A dynamic array such as C++ std::vector stores its elements in one block of memory. When the block is full and a new element arrives, it allocates a block twice as large, copies the existing elements over, and frees the old one.
Start with an empty array of capacity initial_capacity and push pushes elements one by one. Before each push, if size == capacity, reallocate: count one reallocation, add the current size to the copied elements, and double the capacity.
Implement dynamic_array_growth(pushes, initial_capacity).
Input
pushes: How many elements are pushed.
initial_capacity: The capacity of the empty array.
Output
Return [reallocations, copied_elements, final_capacity].
Constraints
0 ≤ pushes ≤ 10^7
1 ≤ initial_capacity ≤ 10^6
Examples
Input:
pushes = 5
initial_capacity = 1
Expected output:
expected = [3, 7, 8]Input:
long long pushes = 5;
long long initial_capacity = 1;
Expected output:
std::vector<long long> expected = {3, 7, 8};Input:
long pushes = 5;
long initial_capacity = 1;
Expected output:
long[] expected = new long[] {3, 7, 8};Explanation
Capacity grows 1 → 2 → 4 → 8 when pushing the 2nd, 3rd and 5th elements, copying 1 + 2 + 4 = 7 elements: [3, 7, 8].
Input:
pushes = 4
initial_capacity = 4
Expected output:
expected = [0, 0, 4]Input:
long long pushes = 4;
long long initial_capacity = 4;
Expected output:
std::vector<long long> expected = {0, 0, 4};Input:
long pushes = 4;
long initial_capacity = 4;
Expected output:
long[] expected = new long[] {0, 0, 4};Explanation
All four elements fit in the first block, so nothing is reallocated: [0, 0, 4].
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
A reallocation happens only when the array is full.
Hint 2
Each time, all current elements are copied and the capacity doubles.
Hint 3
You can jump from one doubling to the next instead of simulating every push.
Expected complexity
O(log pushes) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.