Finding an efficient algorithm

Question

    You are developing a smartphone app. You have a list of potential
    customers for your app. Each customer has a budget and will buy the app at
    your declared price if and only if the price is less than or equal to the
    customer's budget.
    You want to fix a price so that the revenue you earn from the app is
    maximized. Find this maximum possible revenue.
    For instance, suppose you have 4 potential customers and their budgets are
    30, 20, 53 and 14. In this case, the maximum revenue you can get is 60.
**Input format**
Line 1 : N, the total number of potential customers.
Lines 2 to N+1: Each line has the budget of a potential customer.
**Output format**
The output consists of a single integer, the maximum possible revenue you
can earn from selling your app.

  Also, upper bound on N is 5*(10^5) and upper bound on each customer's budget is 10^8.

This is a problem I'm trying to solve . My strategy was to sort the list of budgets and then multiply each of those with its position-index in the sequence - and then print the max of the resulting sequence. However this seems to be quite time-inefficient (at least in the way I'm implementing it - I've attached the code for reference). My upper bound on time is 2 seconds. Can anyone help me find a more time-efficient algorithm (or possibly a more efficient way to implement my algorithm) ?

Here is my solution :

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

using namespace std;

long long max(long long[],long long);
void quickSortIterative(long long[],long long,long long);
long long partition(long long[],long long,long long);
void swap(long long*,long long*);

int main(){
    long long n,k=1;
    scanf("%lld",&n);
    if(n<1 || n > 5*((long long)pow(10,5))){
        exit(0);
    }
    long long budget[n],aux[n];
    for(long long i=0;i<n;i++){
        scanf("%lld",&budget[i]);
        if(budget[i]<1 || budget[i] > (long long)pow(10,8)){
             exit(0);
        }
    }
    quickSortIterative(budget,0,n-1);
    for(long long j=n-1;j>=0;j--){
        aux[j] = budget[j]*k;
        k++;
    }
    cout<<max(aux,n);
    return 0;
}

long long partition (long long arr[], long long l, long long h){
    long long x = arr[h];
    long long i = (l - 1);

    for (long long j = l; j <= h- 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            swap (&arr[i], &arr[j]);
        }
    }
    swap (&arr[i + 1], &arr[h]);
    return (i + 1);
}

void swap ( long long* a, long long* b ){
    long long t = *a;
    *a = *b;
    *b = t;
}

void quickSortIterative(long long arr[], long long l, long long h){
    long long stack[ h - l + 1 ];
    long long top = -1;
    stack[ ++top ] = l;
    stack[ ++top ] = h;
    while ( top >= 0 ){

        h = stack[ top-- ];
        l = stack[ top-- ];
        long long p = partition( arr, l, h );
        if ( p-1 > l ){
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        }
        if ( p+1 < h ){
            stack[ ++top ] = p + 1;
            stack[ ++top ] = h;
        }
    }
} 

long long max(long long arr[],long long length){
    long long max = arr[0];
    for(long long i=1;i<length;i++){
        if(arr[i]>max){
            max=arr[i];
        }
    }
    return max;
}

Answer 1

The following solution is in C programming Language.

The Approach is:

1. Input the number of customers.
2. Input the budgets of customers.
3. Sort the budget.
4. Assign revenue=0
5. Iterate through the budget and Multiply the particular budget with the remaining budget values.
6. If the previous-revenue < new-revenue. assign the new-revenue to revenue variable.

The code is as follows:

#include <stdio.h>

int main(void) {
int i,j,noOfCustomer;

scanf("%d",&noOfCustomer);
long long int budgetOfCustomer[noOfCustomer],maximumRevenue=0;

for(i=0;i<noOfCustomer;i++)
{
    scanf("%Ld",&budgetOfCustomer[i]);
}

for(i=0;i<noOfCustomer;i++)
{
    for(j=i+1;j<noOfCustomer;j++)
    {
        if(budgetOfCustomer[i]>budgetOfCustomer[j])
        {
           budgetOfCustomer[i]=budgetOfCustomer[i] + budgetOfCustomer[j];
           budgetOfCustomer[j]=budgetOfCustomer[i] - budgetOfCustomer[j];
           budgetOfCustomer[i]=budgetOfCustomer[i] - budgetOfCustomer[j];    
        }
       
    }
}


for(i=0;i<noOfCustomer;i++)
{
    budgetOfCustomer[i]=budgetOfCustomer[i]*(noOfCustomer-i);
}

for(i=0;i<noOfCustomer;i++)
{
    if(maximumRevenue<budgetOfCustomer[i])
    maximumRevenue=budgetOfCustomer[i];
}
printf("%Ld\n",maximumRevenue);

return 0;
}

Answer 2

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

int main() {
// your code goes here
long long n;
std::cin >> n;
long long a[n];
for(long long i=0;i<n;i++)
{
    std::cin >> a[i];
}
sort(a,a+n);
long long max=LONG_MIN,count;
for(long long i=0;i<n;i++)
{
    if(a[i]*(n-i)>max)
    {
        max=a[i]*(n-i);
    }
}
std::cout << max << std::endl;
return 0;
}

Answer 3

passed all the test cases

n=int(input())
r=[]
for _ in range(n):
    m=int(input())
    r.append(m)
m=[]
r.sort()
l=len(r)
for i in range(l):
    m.append((l-i)*r[i])

print(max(m))

Answer 4

I dont know if my answer is right or wrong please point out mistakes if there is any

#include<stdio.h>
void main()
{
    register int i,j;
    long long int n,revenue;
    scanf("%Ld",&n);
    long long int a[n];
    for(i=0;i<n;i++)
        scanf("%Ld",&a[i]);
    for (i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(a[i]>a[j])
            {
                a[i]=a[i]+a[j];
                a[j]=a[i]-a[j];
                a[i]=a[i]-a[j];
            }
        }
    }
    for(i=0;i<n;i++)
        a[i]=(n-i)*a[i];
    revenue=0;
    for(i=0;i<n;i++)
    {
        if(revenue<a[i])
            revenue=a[i];
    }
    printf("%Ld\n",revenue);
}

Answer 5

I have used STL library function sort() of C++. It's time complexity is O(nlogn). Here, you just need to sort the given array and check from maximum value to minimum value for given solution. It is O(n) after sorting.

My code which cleared all the test cases :

#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <iostream>

using namespace std;

int main(){
     long long n, a[1000000], max;
     int i, j;
     cin>>n;

     for(i = 0; i < n; i++){
        cin>>a[i];
     }

     sort(a, a + n);
     max  = a[n - 1];
     for(i = n - 2; i >= 0; i--){
         //printf("%lld ", a[i]);
        if(max < (a[i] * (n - i)))
            max = a[i] * (n - i);
     }

     cout<<max<<endl;
     return 0;
} 

Answer 6

You might use qsort in C or std::sort in C++, which is most likely faster than your own code.

Also, your "stack" array will cause you trouble if the difference h - l is large.

Answer 7

Quicksort can take O(n^2) time for certain sequences (often already sorted sequences are bad).

I would recommend you try using a sorting approach with guaranteed O(nlogn) performance (e.g. heapsort or mergesort). Alternatively, you may well find that using the sort routines in the standard library will give better performance than your version.