Sell All the Cars Codechef Solution

Sell All the Cars Codechef Solution: Chef owns NN cars (numbered 11 through NN). He wishes to sell all of them over NN years by selling exactly one car per year. For each valid ii, the initial price of the ii-th car is PiPi. Due to depreciation, the price of each car decreases by 11 unit per year until it is sold.

Note that the price of a car cannot drop below 00 no matter how many years have passed, i.e. when the price of a car reaches 00 in some year, it remains 00 in all subsequent years.

Find the maximum profit Chef can make if he sells his cars in an optimal way. Since this number may be large, compute it modulo 1,000,000,0071,000,000,007 (109+7109+7).

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers P1,P2,…,PNP1,P2,…,PN.

Output

For each test case, print a single line containing one integer ― the maximum profit Chef can make, modulo 1,000,000,0071,000,000,007.

Constraints

  • 1≤T≤251≤T≤25
  • 1≤N≤1051≤N≤105
  • 0≤Pi≤1090≤Pi≤109 for each valid ii

Sample Input 1 

2
3
6 6 6
3
0 1 0

Sample Output 1 

15
1

Explanation

Example case 1:

  • During the first year, Chef’s profit so far is 00 and the prices of the cars are [6,6,6][6,6,6]. Chef sells one of these cars.
  • During the second year, Chef’s profit so far is 66 and the prices of the remaining cars are [5,5][5,5]. Again, Chef sells one of these cars.
  • During the third year, Chef’s profit so far is 1111 and there is one car with price 44. Chef sells this car.
  • In the fourth year, Chef has sold all of his cars and his profit is 1515. This is the maximum profit he can make.

Example case 2:

  • During the first year, Chef’s profit so far is 00 and the prices of the cars are [0,1,0][0,1,0]. Chef sells the second car.
  • During the second year, Chef’s profit so far is 11 and the prices of the remaining cars are [0,0][0,0]. Chef sells one of these cars.
  • During the third year, Chef’s profit so far is 11 and there is one car with price 00. Chef sells this car.
  • During the fourth year, Chef has sold all his cars and his profit is 11

Sell All the Cars  – CodeChef Solution in JAVA

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.stream.IntStream;
public class Main {
    static final int MODULUS = 1_000_000_007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 0; tc < T; ++tc) {
            int N = sc.nextInt();
            int[] P = new int[N];
            for (int i = 0; i < P.length; ++i) {
                P[i] = sc.nextInt();
            }
            System.out.println(solve(P));
        }
        sc.close();
    }
    static int solve(int[] P) {
        int[] sorted = Arrays.stream(P).boxed().sorted(Collections.reverseOrder()).mapToInt(x -> x).toArray();
        return IntStream.range(0, sorted.length).map(i -> Math.max(0, sorted[i] - i)).reduce(Main::addMod).getAsInt();
    }
    static int addMod(int x, int y) {
        return (x + y) % MODULUS;
    }
}

Sell All the Cars  – CodeChef Solution in CPP

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int main()
{
    long long t;
    cin>>t;
    while(t--)
    {
        long long n;
        cin>>n;
        vector <long long> p;
        for(int i=0;i<n;i++)
        {
            long long a;
            cin>>a;
            p.push_back(a);
        }
        long long sum=0;
        sort(p.begin(),p.end(),greater<int>());
        for(int i=0;i<n;i++)
        {
            if((p[i]-i)>0)  sum+=(p[i]-i);
            sum%=mod;
        }
        cout<<sum<<endl;
    }
    return 0;
}

Sell All the Cars- CodeChef Solution in Python

t = int(input())
m = 1000000007
for i in range(t):
    n = int(input())
    cars = sorted(list(map(int, input().split())), reverse=True)
    profit = 0
    x = 0
    for i in cars:
        if i - x > 0:
            profit += (i - x)
        else:
            break
        x += 1
    print(profit % m)

Disclaimer: The above Problem (Sell All the Cars ) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment