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.
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.