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
}
