### jd_sal's blog

By jd_sal, history, 4 weeks ago, , Given an array of integers say A and a number k.One operation means choosing an index i of array and increasing A[i] by 1.You can use this operation on a particular index multiple times.You perform at most k operations(not necessarily on a single index) on this array after which some number X is repeated maximum number of times say Y, then print Y,X.If for a Y, multiple X exist then print the smallest such X. For example let A=[1,9,11,19] and k=10. We can form [9,9,11,19],[1,11,11,19],[1,9,19,19] so answer will be X=9, Y=2.

Constraints : A.size()<=10^5 and 0<=K<=10^9 and -10^9<=A[i]<=10^9.

I can do it in O(n^2) but it's obviously not optimal. Any idea how to proceed?

It's not from any ongoing contest.  Comments (1)
 » 4 weeks ago, # | ← Rev. 3 →   Sort $a$, and let's fix any index $i$. The optimal strategy, provided that we have to apply the operation on $i$ is to increase $a_i$ until it's equal to $a_{i+1}$, then increase them both until they're equal to $a_{i+2}$, and so on. This guarantees that we equalize the most elements, since we have to apply the operation to $i$. If we can find the answer for each $i$, then we have our final answer.With this strategy in mind, let's consider how much it costs to convert $a_{i}...a_{j - 1}$ to $a_j$. This is just the sum of the differences between the target value and current value for each element: $\sum_{p = i}^{j - 1} (a_j - a_p) = a_j(j - i) - \sum_{p = i}^{j - 1} a_p$, which is computable in $O(1)$ with prefix sums. For us to be able to convert to $a_j$, this value must be less than or equal to $k$. Our decision problem (can we convert $a_{i}...a_{j - 1}$ to $a_j$) is clearly monotonic, meaning that if we can't convert to $a_j$, we can't convert to $a_{j + 1}$ and if we can convert to $a_j$, we can convert to $a_{j - 1}$. This means we can binary search on our answer, finding the largest valid $j$ where we can convert $a_{i}...a_{j - 1}$ to $a_j$.If we run this binary search for each starting index $i$, then we can just take the maximum. It's clear that because we can only increase, we're only interested in the values of $j$ that are greater than $i$. Each binary search takes $O(logn) * O(1)$, and we do $N$ of them, so the complexity is $O(nlogn)$, which should easily pass.