# Find max amount railway station can earn | LinkedIN

*Question*

This is Linkedin interview program. There are** ‘n’** ticket windows in the railway station, ith window has **ai **tickets available. Price of a ticket is equal to the number of tickets remaining in that window at that time. When **‘m’** tickets have been sold, what’s the maximum amount of money the railway station can earn?

EX:

INPUT: n=2, m=4

a1 = 2, a2 = 5

OUTPUT: 14(2nd window sold 4 tickets so 5+4+3+2)

*Logic*

- Get the no. of ticket windows
**(n)**and the available tickets in each window from the user**(ai)**Ex: n=3, a1=7, a2=4, a3=3 - Sort the array so that we get the window with most tickets available in order.
- Get the no. of tickets sold
**(m)**form user. - Now, we should find the maximum possible cost of each ticket sold. So we decrement the
**m**and the first element in the array. - Add the value of the current element to the
**cost.** - Repeat the same till the second element is lesser than or equal to the first element.
- If the condition fails then move to the next element.
- Finally, print the total cost.

*Program*

#include<stdio.h> int main() { int n,i,temp,k,index,m; int cost=0; //intialize to zero to avoid garbage value printf("Enter no. of ticket windows"); scanf("%d",&n); getchar(); int* a =(int*)malloc(sizeof(int)*n); /*Get no. of available tickets in each window*/ for(i=0;i<n;i++) { printf("Enter a%d: ",i+1); scanf("%d",&a[i]); } /*Bubble Sorting*/ for(i=0;i<n-1;i++) { for(k=0;k<n-i-1;k++) { if(a[k]<a[k+1]) { temp = a[k+1]; a[k+1] = a[k]; a[k] = temp; } } } printf("Enter no. of ticket sold: "); scanf("%d",&m); index=0; for(i=m;i>0;i--) { /*Check for largest element*/ if(a[index]>=a[index+1]) //if current item greater or equal to next item { cost += a[index]; --a[index]; //decrement no. of tickets in that window } else{ ++index; //move to next window with more tickets cost += a[index]; --a[index]; } } printf("Max Cost is %d",cost); //Maximum cost }