pj_2103's blog

By pj_2103, history, 7 weeks ago, In English

Their are n number of children each of which have a[i] number of toffees. You have k extra number of toffees, you have to distribute less than or equal to k no of toffees such that maximum number of children have equal number of toffees. You have to find out the maximum number of children that will have equal number of toffees after the distribution of the toffees.

Constraints : Time complexity less than or equal to O(n*log(n)).

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem source?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

We can easily see that the number of toffees that the maximum number of children have is one of n original ai (toffees), so you just need to sort then use prefix sum or something similar.