Minimum Groups to Deactivate Transformers

Problem n transformers each belong to a group (groups[]). Deactivation is all-or-nothing per group. Find the minimum number of groups to deactivate so that at least ceil(n/2) transformers are deactivated.

Input / Output

• Input: int array groups (group id per transformer).
• Output: minimum group count.

Constraints

• n up to 10^5; O(n log n) expected.

Example

• groups = [1,1,1,2,2,3] (sizes 3,2,1), threshold ceil(6/2)=3 → 1 (deactivate group 1 alone).

Expected approach

• Count group sizes (hash map), sort sizes descending, greedily take largest groups until the running total ≥ ceil(n/2); the count taken is the answer. Exchange argument justifies the greedy: any optimal solution can swap a smaller chosen group for an unchosen larger one without hurting coverage. O(n log n) time. Edge: threshold arithmetic with odd n — get ceil right.