How to solve this question

help
,
#1

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:

  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}.

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.

#2

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
#3

How

checks this?

1 Like
#4

Thanks a lot.

1 Like
#5

Sorry, I interchanged mid and A, my bad…