codeforces 160A Twins program in java

Twins.java

import java.util.Arrays;
import java.util.Scanner;

public class Twins
{
    public static void main(String[] args)
    {
        Scanner z=new Scanner(System.in);
        int n=z.nextInt();
        int []a=new int[n];
        int tot=0;
        for(int i=0;i<n;i++){
            a[i]=z.nextInt();
            tot+=a[i];
        }
        tot=tot/2;
        Arrays.sort(a);
        int k=0,k1=0;
        for(int i=n-1;i>0;i--)
        {
            k1+=a[i];
            if(k1>tot)
                break;
            else
                k++;
        }
        System.out.println(k+1);
    }
}

Twins Problem Solution

You can also use a PriorityQueue to efficiently select the largest coins first.
This code reduces the time complexity to O(n log n)

import java.util.*;

public class Twins {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // Read number of coins
        int n = sc.nextInt();
        
        // Max-heap to keep coins in descending order
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int tot = 0;
        
        // Read each coin's value and calculate the total sum
        for (int i = 0; i < n; i++) {
            int value = sc.nextInt();
            maxHeap.add(value);
            tot += value;
        }
        
        // Target is half of the total sum
        int target = tot / 2;
        int sum = 0;
        int count = 0;
        
        // Keep picking the largest coins until their sum exceeds half of the total
        while (sum <= target) {
            sum += maxHeap.poll(); // Add the largest remaining coin
            count++;
        }
        
        // Output the minimum number of coins needed
        System.out.println(count);
    }
}