समस्या
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].
सीमाएँ
0 ≤ pushes ≤ 10^7
1 ≤ initial_capacity ≤ 10^6
उदाहरण
इनपुट:
pushes = 5
initial_capacity = 1
अपेक्षित आउटपुट:
expected = [3, 7, 8]इनपुट:
long long pushes = 5;
long long initial_capacity = 1;
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 7, 8};इनपुट:
long pushes = 5;
long initial_capacity = 1;
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 7, 8};व्याख्या
Capacity grows 1 → 2 → 4 → 8 when pushing the 2nd, 3rd and 5th elements, copying 1 + 2 + 4 = 7 elements: [3, 7, 8].
इनपुट:
pushes = 4
initial_capacity = 4
अपेक्षित आउटपुट:
expected = [0, 0, 4]इनपुट:
long long pushes = 4;
long long initial_capacity = 4;
अपेक्षित आउटपुट:
std::vector<long long> expected = {0, 0, 4};इनपुट:
long pushes = 4;
long initial_capacity = 4;
अपेक्षित आउटपुट:
long[] expected = new long[] {0, 0, 4};व्याख्या
All four elements fit in the first block, so nothing is reallocated: [0, 0, 4].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
A reallocation happens only when the array is full.
संकेत 2
Each time, all current elements are copied and the capacity doubles.
संकेत 3
You can jump from one doubling to the next instead of simulating every push.
अपेक्षित जटिलता
O(log pushes) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।