« Maximum profit on app

Problem

You have made a smartphone app and want to set its subscription price such that the profit earned is maximised. There are certain users who will subscribe to your app only if their budget is greater than or equal to your price.

You will be provided with a list of size N having budgets of subscribers and you need to return the maximum profit that you can earn.

Lets say you decide that price of your app is Rs. x and there are N number of subscribers. So maximum profit you can earn is :

m * x where m is total number of subscribers whose budget is greater than or equal to x.

Input format :

Line 1 : N (No. of subscribers)

Line 2 : Budget of subscribers (separated by space)

Output Format :

Maximum profit

Constraints :

1 <= N <= 10^6

1 <=budget[i]<=9999

Sample Input 1 :

4

30 20 53 14

Sample Output 1 :

60

Sample Output 1 Explanation :

Price of your app should be Rs. 20 or Rs. 30. For both prices, you can get the profit Rs. 60.

Sample Input 2 :

5

34 78 90 15 67

Sample Output 2 :

201

Sample Output 2 Explanation :

Price of your app should be Rs. 67. You can get the profit Rs. 201 (i.e. 3 * 67).

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int maximumProfit(int budget[], int n)
15{
16    sort(budget, budget + n, greater<int>());
17
18    int profit = 0;
19
20    for (int i = 0; i < n; i++)
21    {
22        if (budget[i] * (i + 1) > profit)
23        {
24            profit = budget[i] * (i + 1);
25        }
26    }
27    return profit;
28}
29
30int main()
31{
32    int n, *input, i, *cost;
33    cin >> n;
34    input = new int[n];
35    for (i = 0; i < n; i++)
36    {
37        cin >> input[i];
38    }
39
40    cout << maximumProfit(input, n) << endl;
41
42    return 0;
43}