समस्या
C++ std::vector जैसा एक dynamic array अपने elements को memory के एक block में store करता है। जब block भर जाता है और एक नया element आता है, तो यह twice as large block allocate करता है, मौजूद elements को copy करता है, और पुराने block को free कर देता है.
initial_capacity capacity वाले एक खाली array से शुरू करें और pushes elements को एक-एक करके push करें। हर push से पहले, अगर size == capacity है, तो reallocate करें: एक reallocation गिनें, current size को copied elements में जोड़ें, और capacity को double करें.
dynamic_array_growth(pushes, initial_capacity) implement करें.
Input
pushes: कितने elements push किए जाते हैं.
initial_capacity: खाली array की capacity.
Output
[reallocations, copied_elements, final_capacity] return करें.
सीमाएँ
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 1 → 2 → 4 → 8 तक तब बढ़ती है जब 2nd, 3rd और 5th elements push किए जाते हैं, और 1 + 2 + 4 = 7 elements copy होते हैं: [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};व्याख्या
चारों elements पहले block में fit हो जाते हैं, इसलिए कुछ भी reallocate नहीं होता: [0, 0, 4].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
दोबारा मेमोरी तभी ली जाती है जब ऐरे भरा हो।
संकेत 2
हर बार सारे मौजूदा एलिमेंट कॉपी होते हैं और क्षमता दोगुनी हो जाती है।
संकेत 3
हर push को दोहराने के बजाय एक दोगुने से अगले दोगुने पर कूद सकते हैं।
अपेक्षित जटिलता
समय O(log pushes), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।