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.