Recently encountered this question in a placement test.
I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by 𝐵 and the size of the group be 𝐴.
I need to find the maximum number of groups with the exact same contents and of size 𝐴 that can be made from the elements of 𝐵. 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 𝐵.
Example:
- 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}.
- 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}.
Length of 𝐵 can be as large as 10^5 and 𝐴 can also be as large as 10^5.
Please help me find a greedy or dynamic approach to the problem and how to solve it.
In the explanation, maximum number of groups is denoted by k.
So this would have been my logic:
Lets make an array x with x_i = true if there is an answer in which k = i, else x_i = false
Claim: The array x will be TTT.....TF....FFFF
(i.e there is a point p in the array, before which the values of the array are true, and starting from the point till the end, the answer is false)
Proof
Lets assume the opposite, there is a position p in the array, such that x_{p - 1} = false and x_p = true.
But if x_p = true, then we can make p - 1 groups just by removing the last group. Thus, we have arrived at a contradiction.
Now k = p, such that, x_p = true and x_{p+1} = false.
This can be easily done by binary search on the array, and for each mid value, check naively.
One of the methods
Maintaining a frequency map of B before the binary search. Now, when we binary search, let the value we are checking for be mid. Suppose for an element B[i] the number of times it occurs in the array is y. We can add y / mid occurrences to our answer. (Because (y / mid) * mid \leq mid). If the total answer \geq A, we can check the right part of the array, else the left part.
Edit: Time complexity is O(B *log B)
2 Likes
Sorry, I interchanged mid and A, my bad…