We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I solved it via euristic with O(M*SqrtN) solution.
To do that required split initial array by batched with size SqrtN for 10^5 it will be 316.
Hence we have 316 batches with size 316 inside each.
After that you need simulate both type of operations.
To handle each query required SqrtN operations, but after each query size of batches maybe increased by 2.
To avoid growing of count of batches required rebuild all array every SqrtN operations.
What we have:
1) Required rebuild all array M / SqrtN times with O(N) complexity it will be O(M * SqrtN)
2) Each query will take SqrtN operation and it is required to run M times, it will be O(M * SqrtN).
As result we have O(M * SqrtN) complexity.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Array and simple queries
You are viewing a single comment's thread. Return to all comments →
I solved it via euristic with O(M*SqrtN) solution. To do that required split initial array by batched with size SqrtN for 10^5 it will be 316. Hence we have 316 batches with size 316 inside each. After that you need simulate both type of operations. To handle each query required SqrtN operations, but after each query size of batches maybe increased by 2. To avoid growing of count of batches required rebuild all array every SqrtN operations.
What we have: 1) Required rebuild all array M / SqrtN times with O(N) complexity it will be O(M * SqrtN) 2) Each query will take SqrtN operation and it is required to run M times, it will be O(M * SqrtN).
As result we have O(M * SqrtN) complexity.