Optimization of a hackerrank algorithm

Question

I got asked this on hacker rank and I haven't figured out a solution that didn't run out of allotted time. I used php and allotted time was 9 seconds...

The idea is there are "ticket stalls" with a certain number of tickets, say 9. Any ticket they sell is priced at the number of tickets that remain, so first ticket would be $9, second $8 etc...

You're given two lines of data, say:

2 4
1 5

The first row contains two numbers:

1. The number of stalls
2. How many tickets are sold

The second line contains a list of how many tickets each stall has initially, so in this case stall 1 has 1 ticket, stall 2 has 5 tickets.

The problem: what is the maximum amount of money you can make selling the given number of tickets?

In this case, you sell four tickets from stall two for a price of 5 + 4 + 3 + 2 = $14

So how do you solve it. I figured out two ways, both of which ran out of time

1. Load the stall numbers (second line) into an array. Go through that array N times (the number of tickets to sell) picking the largest number out, adding it on to an aggregator, decreasing that number. Then you have the total in the aggregator.

2. Load the stall numbers into an array. Sort the array. Go backwards through the array and as you do: store that number (current), add it to the aggregator, go to the next value. If it is the same (current), then add it to aggregator, subtract 1 from it, keep going. If it is different, go back to the end of the array and start again. Do that N times (the internal loop, not the external one).

The problem: neither one worked.

Can anyone think of a better solution?

Answer 1

1. Create an array of the number of stalls that have an amount of tickets remaining. (so {0, 3, 0, 2} means 2 stalls have three tickets and 3 stalls have one ticket)
2. decrement the highest non-zero entry, increment the entry below it, and add that entry's index to your total.
3. repeat #2 once for every ticket sold.

There's also an obvious way to improve this by multiplying out by MIN(count in highest stall, remaining tickets to be sold).

NOTE: in order for this to perform well, your implementation language must have true arrays (i.e., constant access time, regardless of the index). I do not know PHP, but some languages (JS?) use sequential lists to mimic arrays, but do not have the same performance.

---

Below is the Java implementation of the mentioned approach (read through comments to understand better):

        int[] stalls = new int[] { 4, 7, 1, 4, 8, 8 };
        int t = 4;

        Arrays.sort(stalls);

        int tickets = stalls[stalls.length - 1];
        int[] dp = new int[tickets + 1];

        for (int i = 0; i < stalls.length; i++) {
            dp[stalls[i]]++;
        }

        int total = 0;
        int i = dp.length - 1;

        while (t > 0) {
            if (dp[i] > 0) {
                total += i;
                t--;
                dp[i]--;
                dp[i - 1]++;
            } else {
                i--;
            }
        }

        System.out.println(total);

Answer 2

If you are afraid of DP, this is the O(n) solution you should try. Following code considers only the largest element and go on decreasing it until we reach the required ticket count. It keeps track of multiplication factor by storing it as value in hashMap. In the end if number of tickets is greater than required tickets, it subtracts recently added ticket price from the result until number of tickets becomes equal to required tickets.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TicketClass {
    public static void main(String[] args){
        int[] arr = {10,10,2,8,6,4};
        int ticket = 23;
        Arrays.sort(arr);
        int mul = 1;
        int k = 0;
        System.out.print("Hello World");
        long res = 0;
        Map<Integer,Integer> hm = new HashMap<>();
        for(int i:arr){
            if(hm.containsKey(i)){
                hm.put(i,hm.get(i)+1);
            }
            else
                hm.put(i,1);
        }

        int curr = arr[arr.length-1];

        while(k < ticket){
            mul=hm.getOrDefault(curr,mul);
            res += curr*mul;
            curr--;
            k += mul;
            if(hm.containsKey(curr))
                hm.put(curr,hm.get(curr)+mul);
        }

//End of while loop
        curr++;
        while(k > ticket){
            k--;
            res -=curr;
        }
        System.out.println("ticket "+k);
        System.out.println(res);
    }
}