1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – narek Bojikian Jan 12 at 9:07
  • 1
    $\begingroup$ @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? $\endgroup$ – Debarun Mukherjee Jan 12 at 11:15
  • $\begingroup$ Can you credit the original source where you encountered this task? $\endgroup$ – D.W. Jan 12 at 19:35
  • $\begingroup$ @D.W. It's part of an interview coding round problem from a company. I got this question from a senior at my college. $\endgroup$ – Debarun Mukherjee Jan 12 at 19:46
1
$\begingroup$

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|).$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.