Difficulty: Medium

Prerequisites: Sorting

Problem link:

Contest problem link

Practice problem link


Given number of people of each party, task is to find the sum of minimum number of parties required to aquire the majority vote.


One way of solving the problem is to create count array where each index represents a party. Then sort that count array. Start adding up the elements of the sorted array from the last index till we get maximum stability (majority votes).

This can be done in O(nlog n) complexity if we sort array by divide and conqure technique.

Problem solution: SOLUTION