The Squid Game - Codechef Solution

"Let the games begin."

Squid Game has become a blockbuster hit and the frontman is now finding it difficult to accommodate all the participants in Squid Game 2.0. So, he decided that he will allow only those participants who could solve the following problem.

There are a total of N$N$ players who are competing in the Squid Game, numbered from 1$1$ to N$N$. When the ith$i^{\text{th}}$ player gets eliminated from the game, Ai$A_i$ amount of money is added to the prize pool. The game is played until N−1$N-1$ players get eliminated, and the only player left is declared as the winner. The winner gets all the money present in the prize pool.

You are given an array A$A$ consisting of N$N$ elements, where Ai$A_i$ denotes the prize money added to the prize pool when the ith$i^{\text{th}}$ player gets eliminated from the game. Find the maximum prize that the winner can get, given that you can choose any player to be the winner.

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains an integer N$N$, denoting the number of players.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$, denoting the amount of money added to the prize pool when the ith$i^{\text{th}}$ (1≤i≤N$1\le i\le N$) player dies.

Output Format

For each test case, output in a single line the maximum prize that the winner can get, given that you can choose any player to be the winner.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 2≤N≤105$2\le N\le {10}^5$
• 0≤Ai≤104$0\le A_i\le {10}^4$
• The sum of N$N$ across all test cases does not exceed 106

Sample Input

3

3

3 1 2

5

1 1 1 1 1

6

3 6 4 2 5 1

Sample Output

5 

4

20

Explanation

Test Case 1:
If we choose the first player to be the winner, he will win the game when the second and third players die. Hence, the amount of money won by him will be 1+2=3$1+2=3$.
If we choose the second player to be the winner, he will win the game when the first and third players die. Hence, the amount of money won by him will be 3+2=5$3+2=5$.
If we choose the third player to be the winner, he will win the game when the first and second players die. Hence, the amount of money won by him will be 3+1=4$3+1=4$.
Therefore, we can clearly see that the maximum amount of money that can be won by any player is 5$5$.
Test Case 2: Irrespective of who is chosen, the winner will always win an amount of 4$4$.
Test Case 3: If we choose the sixth player to be the winner, the amount won by him will be 3+6+4+2+5=20$3+6+4+2+5=20$. It can be proven that if we choose any other player to be the winner, the amount is less than 20$20$. Hence, the maximum amount of money that can be won by any player is 20$20$.

Solution In Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc =new Scanner(System.in);
		
		int n = sc.nextInt();
	
		
		for(int i=0;i<n;i++){
		    	int y = sc.nextInt();
		    	int [] arr = new int[y];
		    for(int h=0;h<y;h++){
		        arr[h]=sc.nextInt();
		        }
        
       Arrays.sort(arr);
        int sum =0;
        for(int p=1;p<arr.length;p++){
            sum =sum+arr[p];
        }
        System.out.println(sum);
       
		        }
		        }
             } 
        	

Solution in C++

 #include <iostream>
 #include<bits/stdc++.h>
using namespace std;

int main() 
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n];
       
        for(int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        sort(a,a+n);
        int sum=0;
        for(int i=1; i<n; i++)
        {
            sum+=a[i];
        }
         cout<<sum<<endl;
    }

	return 0;
}
              

Solution in Python

 t = int(input())
for i in range(t):
    sum = 0
    n = int(input())
    lst = list(map(int,input().split()))
    lst.sort(reverse=True)
    m = min(lst)
    for i in lst:
        sum += i
    print(sum-m)