Maximum number of similar groups of a given size that can be made from a given array

Question

I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$.

I need to find the maximum number of groups with the exact same contents and of size $A$ that can be made from the elements of $B$. Once an element is used in a group it is exhausted. A group can have more than one element with the same value as long as the element is still available in $B$.

Example:

1. If the input array is $\{1, 2, 3, 1, 2, 3, 4\}$, and the group size is 3ドル$ the maximum number of groups that can be made is 2ドル$, which are $\{1, 2, 3\}$ and $\{1, 2, 3\}$.
2. If the input array is $\{1, 3, 3, 3, 6, 3, 10\}$, and the group size is 4ドル$ the maximum number of groups that can be made is 1ドル$, which is $\{1, 3, 3, 3\}$.

What I have tried so far, is to frame some equations ( given below ) but after that, I am struggling to come up with an algorithm to solve them.

Let $F_1$ be the frequency of the element $B_1$, $F_2$ be the frequency of the element $B_2$ and so on till $B_n$, where $B_1 \dots B_n$ are distinct elements from the array $B$.

Now I need to choose $n_1, n_2, \dots n_i$ such that

1. $n_1 + n_2 + \dots + n_i = A$
2. $k\cdot n_1 \leq F_1\text{ , } k\cdot n_2 \leq F_2\text{ , }\dots \text{ , }k\cdot n_i \leq F_i$
3. $k$ is the number of groups and we need to maximize it.

Length of $B$ can be as large as 10ドル^5$ and $A$ can also be as large as 10ドル^5$.

Please help me find a greedy or dynamic approach to the problem.

• Narek Bojikian: Hint: try to reduce the problem to a decisional version of it. A decision version is: given $k$: find if it is possible to find a solution of size $k$
• Debarun Mukherjee: @narekBojikian Okay, I thought about an approach by considering it as a decisional problem. $k$ is given, and I have the group with $A$ places to fill. I maintain a priority queue of the frequency array. To fill a place in all the $k$ groups, I do an extract max, subtract $k$ from the frequency val and insert it back into the queue. I do the same until I fill all the $A$ places in all the groups or I am unable to fill it. Is this approach right?
• D.W.: Can you credit the original source where you encountered this task?
• Debarun Mukherjee: @D.W. It's part of an interview coding round problem from a company. I got this question from a senior at my college.

Answer 1

The function $$f:\mathbb{N}\rightarrow\{0, 1\}:f(k) = \begin{cases} 1; &\text{if there is a solution of size $k,ドル}\\ 0; &\text{otherwise} \end{cases} $$ is monoton, since if there is no solution of size $k$ then there is no solution of size $k+1$. That means we can binary search the value of $k$ in the interval $[1, |B|]$, and output the greatest $k$ for which there is a solution of size $k$. Thereby, we turned the problem into a decision problem with an $O(\log |B|)$ factor in the running time.

For a fixed value of $k$, a greedy solution suffices. If we have $F_i$ copies of some element $B_i$, then each set can contain at most $\left\lfloor\frac{F_i}{k}\right\rfloor$ of this element. So we have a solution of size $k$ if and only if $$\sum\limits_{i=1}^{n} \left\lfloor\frac{F_i}{k}\right\rfloor \geq A.$$

As an exercise, try to prove that the greedy solution is optimal. The running time can be bounded in $O(|B|\log|B|).$