Given an array A of size N. You have to perform K operations. Each operation is:
Create a new element equal to the current number of elements.
Decrease other elements by 1.
Any element that is decreased to 0 will be removed.
After that, sort the new array.
Example:
8311 - > 742 - > 6331 - > 5422.
You need to find what the array will be after K operations.
Contraints:
1 ≤ Ai
sum(Ai) ≤ 100
K ≤ 109.
I feel like this's gonna be a cycle detection problem. I've tested a few cases and I see that the cycle length is quite short. But I have no idea what the upperbound will be.
It'd be great if someone can help me prove an upperbound for this, or give me a testcase where the cycle length is large.
Thanks in advance !
