Sell All the Cars Codechef Solution

Hello Programmers In this post, you will know how to solve the Sell All the Cars Codechef Solution.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

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

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

report this adSell 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;
    }
}

report this ad