Interesting Array Problem

Revision en3, by jd_sal, 2019-10-18 00:00:31

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 jd_sal 2019-10-18 00:00:31 35 Tiny change: 'operations on this a' -> 'operations(not necessarily on a single index) on this a'
en2 jd_sal 2019-10-17 23:59:07 40
en1 jd_sal 2019-10-17 23:58:33 669 Initial revision (published)