Twins · Interview Problem

Back to problems

Codeforces

Easy

Arrays

Sorting

Greedy

Twins

Choose the smallest number of coins whose total value is strictly greater than the sum of the remaining coins.

Acceptance 0%

Start Practice

Problem Statement

You are given $n$ coins, each with a positive value. Your task is to pick the minimum number of coins such that the sum of the picked coins is strictly greater than the sum of all remaining coins.

A valid choice always exists if you keep taking the largest-value coins first. Return the minimum number of coins needed.

Input Format

The first line contains an integer $n$ .
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ representing the values of the coins.

Output Format

Print a single integer: the minimum number of coins required.

Constraints

$1 \le n \le 100$
$1 \le a_i \le 100$

Examples

Sample cases returned by the problem API.

Example 1

Input

2
3 3

Output

Explanation

If both coins have value 3, one coin is not strictly greater than the other coin. We need both coins, so the answer is 2.

Example 2

Input

4
3 3 3 3

Output

Explanation

Take any three coins: their sum is 9, which is strictly greater than the remaining coin sum 3.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress