Answer to Question #216934 in C for Laila Singh

Question

You are given some coins. You have to take some coins from the given coins such that the sum of the coins

you took have a value strictly larger than the sum of the rest of the coins. However, you have to take

minimum number of coins while satisfying this condition

Input

In the first line, you are given n (n<=100), the number of integer numbers. In the next line, you will be given n integers, separated by spaces.

Output

Output one number, the minimum number of coins you need to take to have a larger sum than the sum of the

coins you did not take.

Input Output

2 2

3 3

3 2

2 1 2

6 2

4 2 1 2 1 1

In the first sample you will have to take 2 coins. If you take 1 coin, you get sum 3, 3. If you take 0 coins, you get

sums 0, 6. Those variants do not satisfy you as your sum should be strictly more than the other sum.

In the second sample one coin isn't enough for you, too. You can pick coins with values 1, 2 or 2, 2. In any case,

the minimum number of coins equals 2.

.

Answer 1

#include <stdio.h>

int main(void) {
	int n;
	scanf("%d", &n);
	int coins[n];
	int used[n];
	int sum = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &coins[i]);
		sum += coins[i];
		used[i] = 0;
	}
	int needSum = sum / 2 + 1;
	int takenSum = 0;
	
	int usedCoins = 0;
	// on each iteration, the biggest element is found and
	// its value is added to the sum of used coins
	for (int i = 0; i < n; i++) {
		int maxIndex = 0;
		// find maximal value among not used elements
		for (int j = 1; j < n; j++)
			if (!used[i] && coins[j] > coins[maxIndex])
				maxIndex = j;
		used[maxIndex] = 1;
		takenSum += coins[maxIndex];
		usedCoins++;
		if (takenSum >= needSum)
			break;
	}
	printf("%d", usedCoins);
}