Problem statement

https://binarysearch.com/problems/K-Distinct-Groups/

Solution

First of all, let us check(G) be the answer for the question if we can create G groups. How to find this value? First of all, for each frequency which is more than G, we can not use it in full potential, we can use only G times each element. Now, if we have in total G * k elements, it is sufficient and enough to possible to create groups:

  1. If number of elements is < G * k, it is not possible, because we do not have enough elements.
  2. If we have >= G * k elements, then we can do the following: start with first element and distribute always to 1, 2, ..., G, 1, 2, ..., G, ... strategy. In this way, because we do not have frequency more than G we can be sure that now two elements are in the same group and also each group will be filled with exaclty k elements in the end.

Complexity

It is O(n log M) for time and O(1) for space, where M = sum(A) and n = len(A).

Code

class Solution:
    def solve(self, A, k):
        def check(G):
            return sum(min(x, G) for x in A) >= G * k

        beg, end = 0, sum(A) + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid):
                beg = mid
            else:
                end = mid

        return beg