HackerRank ‘Halloween Sale’ Solution

H
Short Problem Definition:

You wish to buy video games from the famous online video game store Mist.

Usually, all games are sold at the same price, p dollars. However, they are planning to have the seasonal Halloween Sale next month in which you can buy games at a cheaper price. Specifically, the first game you buy during the sale will be sold at dollars, but every subsequent game you buy will be sold at exactly d dollars less than the cost of the previous one you bought. This will continue until the cost becomes less than or equal to m dollars, after which every game you buy will cost m dollars each.

Link

Halloween Sale

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

The solution is based on the Arithmetic Progression. It makes it a bit more complex due to the floor m.

Another option is either a while loop or a recursion.

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
// Complete the howManyGames function below.
int howManyGames(int p, int d, int m, int s) {
    int n=floor( (p-m)/d +1);
    if( (n*(2*p-(n-1)*d))/2 <= s)
    {
        return n + (s-(n*(2*p-(n-1)*d)/2))/m;
    }
    else
    {
        return floor(((-d-2*p)+sqrt((-2*p-d)*(-2*p-d)-(8*d*s)))/(-2*d));
    }
}

About the author

Add comment

Archives

Categories