0.4 Devanshi and the Not-So-Fair Share
Devanshi and her twin brother, Devansh, have always been partners in crime—sometimes even when it comes to bending family rules. One morning, their mother had to leave in a rush and emptied her purse, leaving n shiny coins on the table. In her haste, she scribbled a note: “Share the coins equally for your lunch.”
When Devanshi woke up, she found the note—but a mischievous idea struck her. Since Devansh was still snoring, she thought: “Why share fairly when I can grab a bit more?” But she also knew that if she took too many coins, Devansh would notice and create a fuss.
So Devanshi came up with a plan. She decided to:
1. Pick a subset of coins whose total value becomes strictly greater than the value of coins left for Devansh.
2. Out of all possible such selections, she wanted to take the least number of coins to avoid looking suspicious.
Given the values of all the coins on the table, help Devanshi figure out what is the minimum number of coins she must take to ensure her share's total value is strictly greater than Devansh's share.
Constraints
1 <= n <= 100
1 <= ai <= 100
Input Format
The first line contains an integer n - the total number of coins.
The second line contains n space-separated integers a1, a2, ..., an - the value of each coin.
Output Format
Print a single integer - the minimum number of coins Devanshi needs to take to guarantee her share's total value is strictly greater than Devansh’s.
Example 1
Input:
2
3 3
Output:
2
Explanation:
Devanshi has no choice but to take both coins to ensure she has more than Devansh.
Example 2
Input:
3
2 1 2
Output:
2
Explanation:
Explanation: Devanshi can pick coins with values 2 and 2, totaling 4. Devansh will be left with 1. She achieves her goal with just 2 coins.
Log In to solve the Question